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

Session 1

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

Session 2

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

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
  
• Hayley N. Iben, James F. O'Brien, Erik D. Demaine:
  Refolding planar polygons. 71-79
  
• Kevin Buchin, Maike Buchin, Carola Wenk:
  Computing the Fréchet distance between simple polygons in polynomial time. 80-87
  

Session 4

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

Session 5A

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

Session 6

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

Session 7

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

Session 8

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

Session 9

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

Session 10

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

Session 11

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

Session 12

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

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
  
• Esther M. Arkin, Gill Barequet, Joseph S. B. Mitchell:
  Algorithms for two-box covering. 459-467
  
• L. Paul Chew:
  Exact computation of protein structure similarity. 468-474
  

Multimedia abstracts

• Sándor P. Fekete, Alexander Kröller:
  Geometry-based reasoning for a large sensor network. 475-476
  
• Amit Mhatre, Piyush Kumar:
  Projective clustering and its application to surface reconstruction: extended abstract. 477-478
  
• 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
  
• Martin Isenburg, Yuanxin Liu, Jonathan Richard Shewchuk, Jack Snoeyink:
  Illustrating the streaming construction of 2D delaunay triangulations. 481-482
  
• 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
  
• Frank Nielsen, Richard Nock:
  On approximating the smallest enclosing Bregman Balls. 485-486
  

Last update Tue May 21 16:25:30 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page