22. Symposium on Computational Geometry 2006: Sedona, Arizona, USA

Nina Amenta, Otfried Cheong (Eds.): Proceedings of the 22nd ACM Symposium on Computational Geometry, Sedona, Arizona, USA, June 5-7, 2006. ACM 2006, ISBN 1-59593-340-9 BibTeX

Session 1

Wolfgang Mulzer, Günter Rote:
Minimum weight triangulation is NP-hard. 1-10
Electronic Edition (ACM DL) BibTeX
Sunil Arya, Theocharis Malamatos, David M. Mount:
The effect of corners on the complexity of approximate range searching. 11-20
Electronic Edition (ACM DL) BibTeX
Yulai Xie, Jack Snoeyink, Jinhui Xu:
Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope. 21-29
Electronic Edition (ACM DL) BibTeX
Yevgeny Schreiber, Micha Sharir:
An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. 30-39
Electronic Edition (ACM DL) BibTeX
Mathieu Desbrun:
Discrete differential forms and applications to surface tiling. 40
Electronic Edition (ACM DL) BibTeX

Session 2

Noga Alon, Shakhar Smorodinsky:
Conflict-free colorings of shallow discs. 41-43
Electronic Edition (ACM DL) BibTeX
Ke Chen:
How to play a coloring game against a color-blind adversary. 44-51
Electronic Edition (ACM DL) BibTeX
Haim Kaplan, Micha Sharir, Elad Verbin:
Colored intersection searching via sparse rectangular matrix multiplication. 52-60
Electronic Edition (ACM DL) BibTeX

Session 3

Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó, Günter Rote:
Locked and unlocked chains of planar shapes. 61-70
Electronic Edition (ACM DL) BibTeX
Hayley N. Iben, James F. O'Brien, Erik D. Demaine:
Refolding planar polygons. 71-79
Electronic Edition (ACM DL) BibTeX
Kevin Buchin, Maike Buchin, Carola Wenk:
Computing the Fréchet distance between simple polygons in polynomial time. 80-87
Electronic Edition (ACM DL) BibTeX

Session 4

Boris Aronov, Mark de Berg, Chris Gray:
Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. 88-94
Electronic Edition (ACM DL) BibTeX
Esther Ezra, Micha Sharir, Alon Efrat:
On the ICP algorithm. 95-104
Electronic Edition (ACM DL) BibTeX
Marc Glisse:
An upper bound on the average size of silhouettes. 105-111
Electronic Edition (ACM DL) BibTeX

Session 5A

Frédéric Chazal, André Lieutier:
Topology guaranteeing manifold reconstruction using distance function to noisy data. 112-118
Electronic Edition (ACM DL) BibTeX
David Cohen-Steiner, Herbert Edelsbrunner, Dmitriy Morozov:
Vines and vineyards by updating persistence in linear time. 119-126
Electronic Edition (ACM DL) BibTeX
Herbert Edelsbrunner, Dmitriy Morozov, Valerio Pascucci:
Persistence-sensitive simplification functions on 2-manifolds. 127-134
Electronic Edition (ACM DL) BibTeX
Gereon Frahling, Christian Sohler:
A fast k-means implementation using coresets. 135-143
Electronic Edition (ACM DL) BibTeX
David Arthur, Sergei Vassilvitskii:
How slow is the k-means method? 144-153
Electronic Edition (ACM DL) BibTeX
Rajeev Motwani, Assaf Naor, Rina Panigrahy:
Lower bounds on locality sensitive hashing. 154-157
Electronic Edition (ACM DL) BibTeX

Session 6

Lars Arge, Norbert Zeh:
Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching. 158-166
Electronic Edition (ACM DL) BibTeX
Pankaj K. Agarwal, Lars Arge, Ke Yi:
I/O-efficient batched union-find and its applications to terrain analysis. 167-176
Electronic Edition (ACM DL) BibTeX
Esther Moet, Marc J. van Kreveld, A. Frank van der Stappen:
On realistic terrains. 177-186
Electronic Edition (ACM DL) BibTeX
Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos:
Embedding ultrametrics into low-dimensional spaces. 187-196
Electronic Edition (ACM DL) BibTeX
MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Erik D. Demaine, Mohammad Moharrami:
Plane embeddings of planar graph metrics. 197-206
Electronic Edition (ACM DL) BibTeX
James R. Lee:
Volume distortion for subsets of Euclidean spaces: extended abstract. 207-216
Electronic Edition (ACM DL) BibTeX

Session 7

Chee-Keng Yap:
Complete subdivision algorithms, I: intersection of Bezier curves. 217-226
Electronic Edition (ACM DL) BibTeX
Ioannis Z. Emiris, Elias P. Tsigaridas, George M. Tzoumas:
The predicates for the Voronoi diagram of ellipses. 227-236
Electronic Edition (ACM DL) BibTeX
Victor Milenkovic, Elisha Sacks:
An approximate arrangement algorithm for semi-algebraic curves. 237-246
Electronic Edition (ACM DL) BibTeX
Ke Chen, Sariel Har-Peled:
The orienteering problem in the plane revisited. 247-254
Electronic Edition (ACM DL) BibTeX
János Pach, Géza Tóth:
Degenerate crossing numbers. 255-258
Electronic Edition (ACM DL) BibTeX
Eyal Ackerman:
On the maximum number of edges in topological graphs with no four pairwise crossing edges. 259-263
Electronic Edition (ACM DL) BibTeX

Session 8

Rolf Klein, Martin Kutz:
The density of iterated crossing points and a gap result for triangulations of finite point sets. 264-272
Electronic Edition (ACM DL) BibTeX
Micha Sharir, Emo Welzl:
Random triangulations of planar point sets. 273-281
Electronic Edition (ACM DL) BibTeX
Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl:
Pre-triangulations and liftable complexes. 282-291
Electronic Edition (ACM DL) BibTeX
Daniel K. Blandford, Guy E. Blelloch, Clemens Kadow:
Engineering a compact parallel delaunay algorithm in 3D. 292-300
Electronic Edition (ACM DL) BibTeX
Boris Aronov, Paz Carmi, Matthew J. Katz:
Minimum-cost load-balancing partitions. 301-308
Electronic Edition (ACM DL) BibTeX
Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer:
Optimal succinct representations of planar maps. 309-318
Electronic Edition (ACM DL) BibTeX

Session 9

Frédéric Chazal, David Cohen-Steiner, André Lieutier:
A sampling theory for compact sets in Euclidean space. 319-326
Electronic Edition (ACM DL) BibTeX
Joachim Giesen, Edgar A. Ramos, Bardia Sadri:
Medial axis approximation and unstable flow complex. 327-336
Electronic Edition (ACM DL) BibTeX
Jean-Daniel Boissonnat, Steve Oudot:
Provably good sampling and meshing of Lipschitz surfaces. 337-346
Electronic Edition (ACM DL) BibTeX
François Labelle:
Sliver removal by lattice refinement. 347-356
Electronic Edition (ACM DL) BibTeX

Session 10

John Hershberger:
Improved output-sensitive snap rounding. 357-366
Electronic Edition (ACM DL) BibTeX
Eli Packer:
Iterated snap rounding with bounded drift. 367-376
Electronic Edition (ACM DL) BibTeX
Stefan Funke, Christian Klein:
Hole detection or: "how much geometry hides in connectivity?". 377-385
Electronic Edition (ACM DL) BibTeX
Bernard Chazelle, C. Seshadhri:
Online geometric reconstruction. 386-394
Electronic Edition (ACM DL) BibTeX

Session 11

Vladlen Koltun, Micha Sharir:
On overlays and minimization diagrams. 395-401
Electronic Edition (ACM DL) BibTeX
Sariel Har-Peled:
How to get close to the median shape. 402-410
Electronic Edition (ACM DL) BibTeX
Nico Kruithof, Gert Vegter:
Envelope surfaces. 411-420
Electronic Edition (ACM DL) BibTeX

Session 12

Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Francis Lazarus, Kim Whittlesey:
Splitting (complicated) surfaces is hard. 421-429
Electronic Edition (ACM DL) BibTeX
Martin Kutz:
Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. 430-438
Electronic Edition (ACM DL) BibTeX
David W. Krumme, Eynat Rafalin, Diane L. Souvaine, Csaba D. Tóth:
Tight bounds for connecting sites across barriers. 439-448
Electronic Edition (ACM DL) BibTeX

Session 13

Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, Kim Whittlesey:
Minimum-cost coverage of point sets by disks. 449-458
Electronic Edition (ACM DL) BibTeX
Esther M. Arkin, Gill Barequet, Joseph S. B. Mitchell:
Algorithms for two-box covering. 459-467
Electronic Edition (ACM DL) BibTeX
L. Paul Chew:
Exact computation of protein structure similarity. 468-474
Electronic Edition (ACM DL) BibTeX

Multimedia abstracts

Sándor P. Fekete, Alexander Kröller:
Geometry-based reasoning for a large sensor network. 475-476
Electronic Edition (ACM DL) BibTeX
Amit Mhatre, Piyush Kumar:
Projective clustering and its application to surface reconstruction: extended abstract. 477-478
Electronic Edition (ACM DL) BibTeX
Ming-Hung Tsai, Jyh-Da Wei, Jeng-Hung Huang, D. T. Lee:
A portable geometric algorithm visualization system with dynamic camera positioning for tracking 3D objects. 479-480
Electronic Edition (ACM DL) BibTeX
Martin Isenburg, Yuanxin Liu, Jonathan Richard Shewchuk, Jack Snoeyink:
Illustrating the streaming construction of 2D delaunay triangulations. 481-482
Electronic Edition (ACM DL) BibTeX
Ovidiu Daescu, Joseph S. B. Mitchell, Simeon C. Ntafos, James D. Palmer, Chee-Keng Yap:
Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions. 483-484
Electronic Edition (ACM DL) BibTeX
Frank Nielsen, Richard Nock:
On approximating the smallest enclosing Bregman Balls. 485-486
Electronic Edition (ACM DL) BibTeX