23. Symposium on Computational Geometry 2007: Gyeongju, South Korea
Jeff Erickson (Ed.): Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007. ACM 2007 ISBN 978-1-59593-705-6
Session 1A
- Dan Feldman, Morteza Monemizadeh, Christian Sohler: A PTAS for k-means clustering based on weak coresets. 11-18
- Dan Feldman, Amos Fiat, Micha Sharir, Danny Segev: Bi-criteria linear-time approximations for generalized k-mean/median/center. 19-26
Session 1B
- David Eppstein, Michael T. Goodrich, Nodari Sitchinava: Guard placement for efficient point-in-polygon proofs. 27-36
- Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson: Aperture-angle and Hausdorff-approximation of convex figures. 37-45
- Sergey Bereg, Prosenjit Bose, Adrian Dumitrescu, Ferran Hurtado, Pavel Valtr: Traversing a set of points with a minimum number of turns. 46-55
Session 2
- Valentin Polishchuk, Joseph S. B. Mitchell: Thick non-crossing paths and minimum-cost flows in polygonal domains. 56-65
- Jonathan Backer, David G. Kirkpatrick: Finding curvature-constrained paths that avoid polygonal obstacles. 66-73
- Yevgeny Schreiber: Shortest paths on realistic polyhedra. 74-83
- Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang: Querying approximate shortest paths in anisotropic regions. 84-91
Session 3
- David Eppstein: Happy endings for flip graphs. 92-101
- Adrian Dumitrescu, Ichiro Suzuki, Pawel Zylinski: Offline variants of the "lion and man" problem. 102-111
Session 4A: video session
- Frédéric Cazals, Sébastien Loriot: Computing the exact arrangement of circles on a sphere, with applications in structural biology: video. 119-120
- Balint Miklos, Joachim Giesen, Mark Pauly: Medial axis approximation from inner Voronoi balls: a demo of the Mesecina tool. 123-124
- Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan: Kinetic 3D convex hulls via self-adjusting computation. 129-130
- Linqiao Zhang, Hazel Everett, Sylvain Lazard, Sue Whitesides: Towards an implementation of the 3D visibility skeleton. 131-132
Session 4B
- Saurabh Ray, Nabil H. Mustafa: An optimal generalization of the centerpoint theorem, and its extensions. 138-141
- Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, Günter Rote: There are not too many magic configurations. 142-149
Session 5
- Yuanxin Liu, Jack Snoeyink: Quadratic and cubic b-splines by generalizing higher-order voronoi diagrams. 150-157
- Lilian Buzer: Optimal simplification of polygonal chain for rendering. 168-174
- Mohammad Ali Abam, Mark de Berg, Peter Hachenberger, Alireza Zarei: Streaming algorithms for line simplification. 175-183
Session 6
- Jean-Daniel Boissonnat, Leonidas J. Guibas, Steve Oudot: Manifold reconstruction in arbitrary dimensions using witness complexes. 194-203
- Piotr Indyk, Anastasios Sidiropoulos: Probabilistic embeddings of bounded genus graphs into planar graphs. 204-209
- Mirela Ben-Chen, Craig Gotsman, Camille Wormser: Distributed computation of virtual coordinates. 210-219
Session 7
- Pankaj K. Agarwal, Roel Apfelbaum, George B. Purdy, Micha Sharir: Similar simplices in a d-dimensional point set. 232-238
- Saurabh Ray, Nabil H. Mustafa: Weak epsilon-nets have basis of size o(1/epsilon log (1/epsilon)) in any dimension. 239-244
Session 8A
- Hazel Everett, Sylvain Lazard, Daniel Lazard, Mohab Safey El Din: The voronoi diagram of three lines. 255-264
- Julien Demouth, Olivier Devillers, Hazel Everett, Marc Glisse, Sylvain Lazard, Raimund Seidel: Between umbra and penumbra. 265-274
Session 8B
- Darko Dimitrov, Christian Knauer, Klaus Kriegel, Günter Rote: New upper bounds on the quality of the PCA bounding boxes in r2 and r3. 275-283
- Victor Chepoi, Karim Nouioua: Pareto envelopes in R3 under l1 and linfinity distance functions. 284-293
Session 9
- Luis Rademacher: Approximating the centroid is hard. 302-305
- Hans Raj Tiwary: On the hardness of minkowski addition and related operations. 306-309
- Thorsten Bernholt, Friedrich Eisenbrand, Thomas Hofmeister: A geometric framework for solving subsequence problems in computational biology efficiently. 310-318
- Efi Fogel, Dan Halperin, Christophe Weibel: On the exact maximum complexity of Minkowski sums of convex polyhedra. 319-326
Session 10
- Boris Aronov, Sariel Har-Peled, Micha Sharir: On approximate halfspace range counting and relative epsilon-approximations. 327-336
- Yakov Nekrich: A data structure for multi-dimensional range reporting. 344-353
Session 11
- Mohammad Ali Abam, Mark de Berg, Bettina Speckmann: Kinetic KD-trees and longest-side KD-trees. 364-372
- Liam Roditty: Fully dynamic geometric spanners. 373-380
- Pankaj K. Agarwal, Sariel Har-Peled, Hai Yu: Embeddings of surfaces, curves, and moving points in euclidean space. 381-389
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T203413 by the dblp team