21. Symposium on Computational Geometry 2005: Pisa, Italy

Combinatorial geometry

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

Invited Talk

• Pier Francesco Cortese, Giuseppe Di Battista:
  Clustered planarity. 32-34
  

Applications

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

Geometric graphs

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

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
  
• Raimund Seidel, Nicola Wolpert:
  On the exact computation of the topology of real algebraic curves. 107-115
  
• Ee-Chien Chang, Sung Woo Choi, DoYong Kwon, Hyungju Park, Chee-Keng Yap:
  Shortest path amidst disc obstacles is computable. 116-125
  

Metrics and approximation

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

Invited Talk

• Jacob E. Goodman:
  Double-permutation sequences and pseudoline transversals. 159
  

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
  
• Lars Arge, Mark de Berg, Herman J. Haverkort:
  Cache-oblivious r-trees. 170-179
  
• Timothy M. Chan, Eric Y. Chen:
  Multi-pass geometric algorithms. 180-189
  
• Mohammad Ali Abam, Mark de Berg:
  Kinetic sorting and kinetic convex hulls. 190-197
  

Surfaces

• Jean-Daniel Boissonnat, Leonidas J. Guibas, Steve Oudot:
  Learning smooth objects by probing. 198-207
  
• Siu-Wing Cheng, Yajun Wang, Zhuangzhi Wu:
  Provable dimension detection using principal component analysis. 208-217
  
• 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
  

Delaunay meshes

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

Geometry and topology

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

Data structures

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

Optimization problems

• David Eppstein, Kevin A. Wortman:
  Minimum dilation stars. 321-326
  
• Mohammad Farshi, Panos Giannopoulos, Joachim Gudmundsson:
  Finding the best shortcut in a geometric network. 327-335
  
• Friedrich Eisenbrand, Stefan Funke, Andreas Karrenbauer, Domagoj Matijevic:
  Energy-aware stage illumination. 336-345
  
• Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon C. Ntafos, Binhai Zhu:
  Guarding a terrain by two watchtowers. 346-355
  
• 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
  

Video/multimedia presentations

• Jean-Daniel Boissonnat, Leonidas J. Guibas, Steve Oudot:
  Learning smooth objects by probing. 364-365
  
• Tobias Lenz:
  Reconstructing collections of arbitrary curves. 366-367
  
• 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
  
• Ajith Mascarenhas, Jack Snoeyink:
  Implementing time-varying contour trees. 370-371
  
• Sander Florisson, Marc J. van Kreveld, Bettina Speckmann:
  Rectangular cartograms: construction & animation. 372-373
  
• Kim Hansen, Stephen K. Wismath:
  Animation of curve constrained drawings of planar graphs. 374-375
  
• Gill Barequet, Yuval Scharf, Matthew T. Dickerson:
  Covering points with a polygon. 376-377
  
• Ovidiu Daescu, James D. Palmer:
  1-link shortest paths in weighted regions. 378-379
  
• 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
  
• Efi Fogel, Dan Halperin:
  Exact Minkowski sums of convex polyhedra. 382-383
  
• Naga K. Govindaraju, Ming C. Lin, Dinesh Manocha:
  Fast and reliable collision detection using graphics processors. 384-385