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

1

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

2A

Kenneth L. Clarkson:
Tighter bounds for random projections of manifolds. 39-48
Manor Mendel, Assaf Naor:
Markov convexity and local rigidity of distorted metrics. 49-58
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

2B

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

3

Timothy M. Chan:
A (slightly) faster algorithm for klee's measure problem. 94-100
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
Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine, Scott D. Kominers:
Hinged dissections exist. 110-119
Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc:
Helly-type theorems for approximate covering. 120-128

4

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

5A

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

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
Evangelia Pyrga, Saurabh Ray:
New existence proofs epsilon-nets. 199-207
Adrian Dumitrescu, Micha Sharir, Csaba D. Tóth:
Extremal problems on triangle areas in two and three dimensions. 208-217

Video and multimedia presentations

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

7

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

8

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

9A

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

9B

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

10

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