26. Symposium on Computational Geometry 2010: Snowbird, Utah, USA

Monday, June 14 - 9: 00-10: 20 am

• Timothy M. Chan:
  Optimal partition trees. 1-10
  
• Tobias Christ, Dömötör Pálvölgyi, Milos Stojakovic:
  Consistent digital line segments. 11-18
  
• Bernard Chazelle:
  The geometry of flocking. 19-28
  
• Sunil Arya, David M. Mount, Jian Xia:
  Tight lower bounds for halfspace range searching. 29-37
  

Session 2: invited talk

• Helmut Pottmann:
  Discrete geometric structures for architecture. 38
  

Session 3

• Mark de Berg:
  Better bounds on the union complexity of locally fat objects. 39-47
  
• Marc Glisse, Sylvain Lazard:
  On the complexity of sets of free lines and line segments among balls in three dimensions. 48-57
  
• Natan Rubin:
  Lines avoiding balls in three dimensions revisited. 58-67
  

Session 4

• Sergio Cabello, Bojan Mohar:
  Adding one edge to planar graphs makes crossing number hard. 68-76
  
• Joachim Gudmundsson, Pat Morin:
  Planar visibility: testing and counting. 77-86
  
• Pankaj K. Agarwal, Rinat Ben Avraham, Micha Sharir:
  The 2-center problem in three dimensions. 87-96
  
• Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar:
  Linkless and flat embeddings in 3-space and the unknot problem. 97-106
  

Session 5: video presentations

• Gur Harary, Ayellet Tal:
  Visualizing 3D Euler spirals. 107-108
  
• Dmitry N. Krasnoshchekov, Valentin Polishchuk, Arto Vihavainen:
  Shape approximation using k-order alpha-hulls. 109-110
  
• Harish Doraiswamy, Aneesh Sood, Vijay Natarajan:
  Constructing Reeb graphs using cylinder maps. 111-112
  
• Adrian Dumitrescu, Evan Hilscher:
  Convexification of polygons by length preserving transformations. 113-114
  
• Stephen J. Guy, Jur P. van den Berg, Ming C. Lin, Dinesh Manocha:
  Geometric methods for multi-agent collision avoidance. 115-116
  

Session 6A

• Bernard Chazelle:
  A geometric approach to collective motion. 117-126
  
• Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas, Haim Kaplan, Vladlen Koltun, Natan Rubin, Micha Sharir:
  Kinetic stable Delaunay graphs. 127-136
  
• Haim Kaplan, Natan Rubin, Micha Sharir:
  A kinetic triangulation scheme for moving points in the plane. 137-146
  

Session 6B

• Sergio Cabello, Éric Colin de Verdière, Francis Lazarus:
  Output-sensitive algorithm for the edge-width of an embedded graph. 147-155
  
• Sergio Cabello, Éric Colin de Verdière, Francis Lazarus:
  Finding shortest non-trivial cycles in directed graphs on surfaces. 156-165
  
• Tamal K. Dey, Jian Sun, Yusu Wang:
  Approximating loops in a shortest homology basis from point data. 166-175
  

Session 7A

• Florian Berger, Rolf Klein:
  A traveller's problem. 176-182
  
• Joseph S. B. Mitchell:
  A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane. 183-191
  
• Mohammad Ali Abam, Sariel Har-Peled:
  New constructions of SSPDs and their applications. 192-200
  

Session 7B

• Benjamin A. Burton:
  The complexity of the normal surface solution space. 201-209
  
• Keiko Imai, Akitoshi Kawamura, Jirí Matousek, Daniel Reem, Takeshi Tokuyama:
  Distance k-sectors exist. 210-215
  
• Akitoshi Kawamura, Jirí Matousek, Takeshi Tokuyama:
  Zone diagrams in Euclidean spaces and in other normed spaces. 216-221
  

Session 8A

• Karl Bringmann:
  Klee's measure problem on fat boxes in time PARTIAL DIFFERENTIAL (n^(d+2)/3). 222-229
  
• Pankaj K. Agarwal:
  An improved algorithm for computing the volume of the union of cubes. 230-239
  
• Peyman Afshani, Lars Arge, Kasper Dalgaard Larsen:
  Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. 240-246
  
• David M. Mount, Eunhui Park:
  A dynamic data structure for approximate range searching. 247-256
  

Session 8B

• Afra Zomorodian:
  The tidy set: a minimal simplicial set for computing homology of clique complexes. 257-266
  
• William Harvey, Yusu Wang, Rephael Wenger:
  A randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes. 267-276
  
• Benoît Hudson, Gary L. Miller, Steve Oudot, Donald Sheehy:
  Topological inference via meshing. 277-286
  
• Omid Amini, Jean-Daniel Boissonnat, Pooran Memari:
  Geometric tomography with topological guarantees. 287-296
  

Session 9A

• Micha Sharir, Adam Sheffer, Emo Welzl:
  On degrees in random triangulations of point sets. 297-306
  
• Eryk Kopczynski, Igor Pak, Piotr Przytycki:
  Acute triangulations of polyhedra and the Euclidean space. 307-313
  
• Umut A. Acar, Andrew Cotter, Benoît Hudson, Duru Türkoglu:
  Dynamic well-spaced point sets. 314-323
  

Session 9B

• Jean-Daniel Boissonnat, Arijit Ghosh:
  Manifold reconstruction using tangential Delaunay complexes. 324-333
  
• Dominique Attali, André Lieutier:
  Optimal reconstruction might be hard. 334-343
  
• Dominique Attali, André Lieutier:
  Reconstructing shapes with guarantees by unions of convex sets. 344-353
  

Session 10

• Abdul Basit, Nabil H. Mustafa, Saurabh Ray, Sarfraz Raza:
  Improving the first selection lemma in R³. 354-357
  
• Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Rom Pinchasi, Tillmann Miltzow:
  Points with large quadrant-depth. 358-364
  
• Anne Driemel, Sariel Har-Peled, Carola Wenk:
  Approximating the Fréchet distance for realistic curves in near linear time. 365-374
  
• Pankaj K. Agarwal, Boris Aronov, Marc J. van Kreveld, Maarten Löffler, Rodrigo I. Silveira:
  Computing similarity between piecewise-linear functions. 375-383
  

Session 11: invited talk

• Cláudio T. Silva:
  Applications of geometry and topology for quadrilateral meshprocessing and verifiable visualization. 384-385
  

Session 12

• David L. Millman, Jack Snoeyink:
  Computing planar Voronoi diagrams in double precision: a further example of degree-driven algorithm design. 386-392
  
• Gur Harary, Ayellet Tal:
  3D Euler spirals for 3D curve completion. 393-402
  
• Lars Arge, Morten Revsbæk, Norbert Zeh:
  I/O-efficient computation of water flow across a terrain. 403-412
  

Session 13

• György Elekes, Micha Sharir:
  Incidences in three dimensions and distinct distances in the plane. 413-422
  
• János Pach, Andrew Suk, Miroslav Treml:
  Tangencies between families of disjoint regions in the plane. 423-428
  
• David Eppstein, Elena Mumford:
  Steinitz theorems for orthogonal polyhedra. 429-438
  

Last update Thu May 24 04:15:12 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page