21. Symposium on Computational Geometry 2005: Pisa, Italy

Joseph S. B. Mitchell, Günter Rote (Eds.): Proceedings of the 21st ACM Symposium on Computational Geometry, Pisa, Italy, June 6-8, 2005. ACM 2005, ISBN 1-58113-991-8 BibTeX

Combinatorial geometry

János Pach, Gábor Tardos:
Forbidden patterns and unit distances. 1-9
Electronic Edition (ACM DL) BibTeX
Otfried Cheong, Xavier Goaoc, Andreas Holmsen:
Hadwiger and Helly-type theorems for disjoint unit spheres in R³. 10-15
Electronic Edition (ACM DL) BibTeX
György Elekes, Csaba D. Tóth:
Incidences of not-too-degenerate hyperplanes. 16-21
Electronic Edition (ACM DL) BibTeX
Esther Ezra:
Almost tight bound for a single cell in an arrangement of convex polyhedra in R³. 22-31
Electronic Edition (ACM DL) BibTeX

Invited Talk

Pier Francesco Cortese, Giuseppe Di Battista:
Clustered planarity. 32-34
Electronic Edition (ACM DL) BibTeX

Applications

Danny Z. Chen, Xiaobo Sharon Hu, Chao Wang, Xiaodong Wu:
Mountain reduction, block matching, and applications in intensity-modulated radiation therapy. 35-44
Electronic Edition (ACM DL) BibTeX
Eran Eyal, Dan Halperin:
Dynamic maintenance of molecular surfaces under conformational changes. 45-54
Electronic Edition (ACM DL) BibTeX
Sergey Bereg, Adrian Dumitrescu:
The lifting model for reconfiguration. 55-62
Electronic Edition (ACM DL) BibTeX
Ron Wein, Jur P. van den Berg, Dan Halperin:
The Visibility-Voronoi Complex and Its Applications. 63-72
Electronic Edition (ACM DL) BibTeX

Geometric graphs

Sergey Bereg:
Certifying and constructing minimally rigid graphs in the plane. 73-80
Electronic Edition (ACM DL) BibTeX
Michael Hoffmann, Csaba D. Tóth:
Pointed and colored binary encompassing trees. 81-90
Electronic Edition (ACM DL) BibTeX
Oswin Aichholzer, Hannes Krasser:
Abstract order type extension and new results on the rectilinear crossing number. 91-98
Electronic Edition (ACM DL) BibTeX

Exact geometric computation

Eric Berberich, Michael Hemmer, Lutz Kettner, Elmar Schömer, Nicola Wolpert:
An exact, complete and efficient implementation for computing planar maps of quadric intersection curves. 99-106
Electronic Edition (ACM DL) BibTeX
Raimund Seidel, Nicola Wolpert:
On the exact computation of the topology of real algebraic curves. 107-115
Electronic Edition (ACM DL) BibTeX
Ee-Chien Chang, Sung Woo Choi, DoYong Kwon, Hyungju Park, Chee-Keng Yap:
Shortest path amidst disc obstacles is computable. 116-125
Electronic Edition (ACM DL) BibTeX

Metrics and approximation

Sariel Har-Peled, Akash Kushal:
Smaller coresets for k-median and k-means clustering. 126-134
Electronic Edition (ACM DL) BibTeX
Kenneth L. Clarkson, Kasturi R. Varadarajan:
Improved approximation algorithms for geometric set cover. 135-141
Electronic Edition (ACM DL) BibTeX
Gereon Frahling, Piotr Indyk, Christian Sohler:
Sampling in dynamic data streams and applications. 142-149
Electronic Edition (ACM DL) BibTeX
Sariel Har-Peled, Manor Mendel:
Fast construction of nets in low dimensional metrics, and their applications. 150-158
Electronic Edition (ACM DL) BibTeX

Invited Talk

Jacob E. Goodman:
Double-permutation sequences and pseudoline transversals. 159
Electronic Edition (ACM DL) BibTeX

Geometric Algorithms in Alternate Computational Models

Lars Arge, Gerth Stølting Brodal, Rolf Fagerberg, Morten Laustsen:
Cache-oblivious planar orthogonal range searching and counting. 160-169
Electronic Edition (ACM DL) BibTeX
Lars Arge, Mark de Berg, Herman J. Haverkort:
Cache-oblivious r-trees. 170-179
Electronic Edition (ACM DL) BibTeX
Timothy M. Chan, Eric Y. Chen:
Multi-pass geometric algorithms. 180-189
Electronic Edition (ACM DL) BibTeX
Mohammad Ali Abam, Mark de Berg:
Kinetic sorting and kinetic convex hulls. 190-197
Electronic Edition (ACM DL) BibTeX

Surfaces

Jean-Daniel Boissonnat, Leonidas J. Guibas, Steve Oudot:
Learning smooth objects by probing. 198-207
Electronic Edition (ACM DL) BibTeX
Siu-Wing Cheng, Yajun Wang, Zhuangzhi Wu:
Provable dimension detection using principal component analysis. 208-217
Electronic Edition (ACM DL) BibTeX
Tamal K. Dey, Joachim Giesen, Edgar A. Ramos, Bardia Sadri:
Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based surface reconstruction. 218-227
Electronic Edition (ACM DL) BibTeX

Delaunay meshes

Sariel Har-Peled, Alper Üngör:
A time-optimal delaunay refinement algorithm in two dimensions. 228-236
Electronic Edition (ACM DL) BibTeX
Jonathan Richard Shewchuk:
Star splaying: an algorithm for repairing delaunay triangulations and convex hulls. 237-246
Electronic Edition (ACM DL) BibTeX

Geometry and topology

Dominique Attali, Herbert Edelsbrunner:
Inclusion-exclusion formulas from independent complexes. 247-254
Electronic Edition (ACM DL) BibTeX
Frédéric Chazal, André Lieutier:
Weak feature size and persistent homology: computing homology of solids in Rⁿ from noisy data samples. 255-262
Electronic Edition (ACM DL) BibTeX
David Cohen-Steiner, Herbert Edelsbrunner, John Harer:
Stability of persistence diagrams. 263-271
Electronic Edition (ACM DL) BibTeX
David Cohen-Steiner, Herbert Edelsbrunner:
Inequalities for the curvature of curves and surfaces. 272-277
Electronic Edition (ACM DL) BibTeX
Sergey Bereg, David G. Kirkpatrick:
Curvature-bounded traversals of narrow corridors. 278-287
Electronic Edition (ACM DL) BibTeX

Data structures

Mark de Berg:
Vertical ray shooting for fat objects. 288-295
Electronic Edition (ACM DL) BibTeX
David Eppstein, Michael T. Goodrich, Jonathan Z. Sun:
The skip quadtree: a simple dynamic data structure for multidimensional data. 296-305
Electronic Edition (ACM DL) BibTeX
Yakov Nekrich:
Space efficient dynamic orthogonal range reporting. 306-313
Electronic Edition (ACM DL) BibTeX
Alireza Zarei, Mohammad Ghodsi:
Efficient computation of query point visibility in polygons with holes. 314-320
Electronic Edition (ACM DL) BibTeX

Optimization problems

David Eppstein, Kevin A. Wortman:
Minimum dilation stars. 321-326
Electronic Edition (ACM DL) BibTeX
Mohammad Farshi, Panos Giannopoulos, Joachim Gudmundsson:
Finding the best shortcut in a geometric network. 327-335
Electronic Edition (ACM DL) BibTeX
Friedrich Eisenbrand, Stefan Funke, Andreas Karrenbauer, Domagoj Matijevic:
Energy-aware stage illumination. 336-345
Electronic Edition (ACM DL) BibTeX
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon C. Ntafos, Binhai Zhu:
Guarding a terrain by two watchtowers. 346-355
Electronic Edition (ACM DL) BibTeX
Hee-Kap Ahn, Otfried Cheong, Chong-Dae Park, Chan-Su Shin, Antoine Vigneron:
Maximizing the overlap of two planar convex sets under rigid motions. 356-363
Electronic Edition (ACM DL) BibTeX

Video/multimedia presentations

Jean-Daniel Boissonnat, Leonidas J. Guibas, Steve Oudot:
Learning smooth objects by probing. 364-365
Electronic Edition (ACM DL) BibTeX
Tobias Lenz:
Reconstructing collections of arbitrary curves. 366-367
Electronic Edition (ACM DL) BibTeX
Vikas Singh, Lopamudra Mukherjee, Jinhui Xu, Kenneth R. Hoffmann, Guang Xu, Zhenming Chen:
Efficient geometric techniques for reconstructing 3D vessel trees from biplane image. 368-369
Electronic Edition (ACM DL) BibTeX
Ajith Mascarenhas, Jack Snoeyink:
Implementing time-varying contour trees. 370-371
Electronic Edition (ACM DL) BibTeX
Sander Florisson, Marc J. van Kreveld, Bettina Speckmann:
Rectangular cartograms: construction & animation. 372-373
Electronic Edition (ACM DL) BibTeX
Kim Hansen, Stephen K. Wismath:
Animation of curve constrained drawings of planar graphs. 374-375
Electronic Edition (ACM DL) BibTeX
Gill Barequet, Yuval Scharf, Matthew T. Dickerson:
Covering points with a polygon. 376-377
Electronic Edition (ACM DL) BibTeX
Ovidiu Daescu, James D. Palmer:
1-link shortest paths in weighted regions. 378-379
Electronic Edition (ACM DL) BibTeX
A. G. Oliveira, Pedro Jussieu de Rezende, F. P. Selmi-Dei:
An extension of CGAL to the oriented projective plane T² and its dynamic visualization system. 380-381
Electronic Edition (ACM DL) BibTeX
Efi Fogel, Dan Halperin:
Exact Minkowski sums of convex polyhedra. 382-383
Electronic Edition (ACM DL) BibTeX
Naga K. Govindaraju, Ming C. Lin, Dinesh Manocha:
Fast and reliable collision detection using graphics processors. 384-385
Electronic Edition (ACM DL) BibTeX