24. Symposium on Computational Geometry 2008: College Park, MD, USA

Monique Teillaud (Ed.): Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 9-11, 2008. ACM 2008, ISBN 978-1-60558-071-5 BibTeX

1

Timothy M. Chan:
Dynamic coresets. 1-9
Electronic Edition (ACM DL) BibTeX
Ken Been, Martin Nöllenburg, Sheung-Hung Poon, Alexander Wolff:
Optimizing active ranges for consistent dynamic map labeling. 10-19
Electronic Edition (ACM DL) BibTeX
Esther M. Arkin, Joseph S. B. Mitchell, Valentin Polishchuk:
Maximum thick paths in static and dynamic environments. 20-27
Electronic Edition (ACM DL) BibTeX
Krzysztof Onak, Anastasios Sidiropoulos:
Circular partitions with applications to visualization and embeddings. 28-37
Electronic Edition (ACM DL) BibTeX
Alexander I. Bobenko:
Delaunay triangulations of polyhedral surfaces, a discrete Laplace-Beltrami operator and applications. 38
Electronic Edition (ACM DL) BibTeX

2A

Kenneth L. Clarkson:
Tighter bounds for random projections of manifolds. 39-48
Electronic Edition (ACM DL) BibTeX
Manor Mendel, Assaf Naor:
Markov convexity and local rigidity of distorted metrics. 49-58
Electronic Edition (ACM DL) BibTeX
Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Michel Habib, Yann Vaxès:
Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs. 59-68
Electronic Edition (ACM DL) BibTeX

2B

Noga Alon, Dan Halperin, Oren Nechushtan, Micha Sharir:
The complexity of the outer face in arrangements of random segments. 69-78
Electronic Edition (ACM DL) BibTeX
Sarit Buzaglo, Ron Holzman, Rom Pinchasi:
On s-intersecting curves and related problems. 79-84
Electronic Edition (ACM DL) BibTeX
Timothy M. Chan:
On levels in arrangements of curves, iii: further improvements. 85-93
Electronic Edition (ACM DL) BibTeX

3

Timothy M. Chan:
A (slightly) faster algorithm for klee's measure problem. 94-100
Electronic Edition (ACM DL) BibTeX
Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite:
Walking your dog in the woods in polynomial time. 101-109
Electronic Edition (ACM DL) BibTeX
Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine, Scott D. Kominers:
Hinged dissections exist. 110-119
Electronic Edition (ACM DL) BibTeX
Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc:
Helly-type theorems for approximate covering. 120-128
Electronic Edition (ACM DL) BibTeX

4

Pankaj K. Agarwal, Lars Arge, Thomas Mølhave, Bardia Sadri:
I/o-efficient efficient algorithms for computing contours on a terrain. 129-138
Electronic Edition (ACM DL) BibTeX
Lars Arge, Gerth Stølting Brodal, S. Srinivasa Rao:
External memory planar point location with logarithmic updates. 139-147
Electronic Edition (ACM DL) BibTeX
Kenneth L. Clarkson, C. Seshadhri:
Self-improving algorithms for delaunay triangulations. 148-155
Electronic Edition (ACM DL) BibTeX
Bernard Chazelle, Wolfgang Johann Heinrich Mulzer:
Markov incremental constructions. 156-163
Electronic Edition (ACM DL) BibTeX

5A

Eric Berberich, Michael Kerber, Michael Sagraloff:
Exact geometric-topological analysis of algebraic surfaces. 164-173
Electronic Edition (ACM DL) BibTeX
Olivier Devillers, Marc Glisse, Sylvain Lazard:
Predicates for line transversals to lines and line segments in three-dimensional space. 174-181
Electronic Edition (ACM DL) BibTeX
Frédéric Cazals, Aditya Parameswaran, Sylvain Pion:
Robust construction of the three-dimensional flow complex. 182-191
Electronic Edition (ACM DL) BibTeX

5B

Hans Raj Tiwary, Khaled M. Elbassioni:
On the complexity of checking self-duality of polytopes and its relations to vertex enumeration and graph isomorphism. 192-198
Electronic Edition (ACM DL) BibTeX
Evangelia Pyrga, Saurabh Ray:
New existence proofs epsilon-nets. 199-207
Electronic Edition (ACM DL) BibTeX
Adrian Dumitrescu, Micha Sharir, Csaba D. Tóth:
Extremal problems on triangle areas in two and three dimensions. 208-217
Electronic Edition (ACM DL) BibTeX

Video and multimedia presentations

Efi Fogel, Ophir Setter, Dan Halperin:
Arrangements of geodesic arcs on the sphere. 218-219
Electronic Edition (ACM DL) BibTeX
Tamal K. Dey, Joshua A. Levine:
Delpsc: a delaunay mesher for piecewise smooth complexes. 220-221
Electronic Edition (ACM DL) BibTeX
Manuel Caroli, Monique Teillaud:
On the computation of 3d periodic triangulations. 222-223
Electronic Edition (ACM DL) BibTeX
Pavel Emeliyanenko, Michael Kerber:
Visualizing and exploring planar algebraic arrangements: a web application. 224-225
Electronic Edition (ACM DL) BibTeX
Audrey Lee, Ileana Streinu, Louis Theran:
Analyzing rigidity with pebble games. 226-227
Electronic Edition (ACM DL) BibTeX
Jyh-Ming Lien:
Minkowski sums of rotating convex polyhedra. 228-229
Electronic Edition (ACM DL) BibTeX
Joondong Kim, Joseph S. B. Mitchell, Valentin Polishchuk, Arto Vihavainen:
Routing a maximum number of disks through a scene of moving obstacles. 230-231
Electronic Edition (ACM DL) BibTeX

7

Frédéric Chazal, Steve Oudot:
Towards persistence-based reconstruction in euclidean spaces. 232-241
Electronic Edition (ACM DL) BibTeX
Herbert Edelsbrunner, John Harer, Amit K. Patel:
Reeb spaces of piecewise linear mappings. 242-250
Electronic Edition (ACM DL) BibTeX
Erin W. Chambers, Jeff Erickson, Pratik Worah:
Testing contractibility in planar rips complexes. 251-259
Electronic Edition (ACM DL) BibTeX
Eitan Yaffe, Dan Halperin:
Approximating the pathway axis and the persistence diagram of a collection of balls in 3-space. 260-269
Electronic Edition (ACM DL) BibTeX

8

Jean-Daniel Boissonnat, Camille Wormser, Mariette Yvinec:
Locally uniform anisotropic meshing. 270-277
Electronic Edition (ACM DL) BibTeX
Mikhail Belkin, Jian Sun, Yusu Wang:
Discrete laplace operator on meshed surfaces. 278-287
Electronic Edition (ACM DL) BibTeX
Pankaj K. Agarwal, Bardia Sadri, Hai Yu:
Untangling triangulations through local explorations. 288-297
Electronic Edition (ACM DL) BibTeX
Maarten Löffler, Jack Snoeyink:
Delaunay triangulations of imprecise pointsin linear time after preprocessing. 298-304
Electronic Edition (ACM DL) BibTeX
Kenneth L. Clarkson:
Geometry is everywhere, part XLVII: metrics, nets, dimensions, and measures. 305
Electronic Edition (ACM DL) BibTeX

9A

Mohammad Ali Abam, Mark de Berg, Joachim Gudmundsson:
A simple and efficient kinetic spanner. 306-310
Electronic Edition (ACM DL) BibTeX
Luca Castelli Aleardi, Éric Fusy, Thomas Lewiner:
Schnyder woods for higher genus triangulated surfaces. 311-319
Electronic Edition (ACM DL) BibTeX
Minkyoung Cho, David M. Mount:
Embedding and similarity search for point sets under translation. 320-327
Electronic Edition (ACM DL) BibTeX

9B

Naoki Katoh, Shin-ichi Tanigawa:
Fast enumeration algorithms for non-crossing geometric graphs. 328-337
Electronic Edition (ACM DL) BibTeX
Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, Bettina Speckmann, Philipp Zumstein:
Polychromatic colorings of plane graphs. 338-345
Electronic Edition (ACM DL) BibTeX
Jacob Fox, János Pach:
Coloring k_k-free intersection graphs of geometric objects in the plane. 346-354
Electronic Edition (ACM DL) BibTeX

10

Jinhee Chun, Matias Korman, Martin Nöllenburg, Takeshi Tokuyama:
Consistent digital rays. 355-364
Electronic Edition (ACM DL) BibTeX
Ileana Streinu, Louis Theran:
Combinatorial genericity and minimal rigidity. 365-374
Electronic Edition (ACM DL) BibTeX
Vida Dujmovic, Ken-ichi Kawarabayashi, Bojan Mohar, David R. Wood:
Improved upper bounds on the crossing number. 375-384
Electronic Edition (ACM DL) BibTeX
Radoslav Fulek, Andreas Holmsen, János Pach:
Intersecting convex sets by rays. 385-391
Electronic Edition (ACM DL) BibTeX