23. Symposium on Computational Geometry 2007: Gyeongju, South Korea

Session 1A

• Pankaj K. Agarwal, Hai Yu:
  A space-optimal data-stream algorithm for coresets in the plane. 1-10
  
• Dan Feldman, Morteza Monemizadeh, Christian Sohler:
  A PTAS for k-means clustering based on weak coresets. 11-18
  
• Dan Feldman, Amos Fiat, Micha Sharir, Danny Segev:
  Bi-criteria linear-time approximations for generalized k-mean/median/center. 19-26
  

Session 1B

• David Eppstein, Michael T. Goodrich, Nodari Sitchinava:
  Guard placement for efficient point-in-polygon proofs. 27-36
  
• Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson:
  Aperture-angle and Hausdorff-approximation of convex figures. 37-45
  
• Sergey Bereg, Prosenjit Bose, Adrian Dumitrescu, Ferran Hurtado, Pavel Valtr:
  Traversing a set of points with a minimum number of turns. 46-55
  

Session 2

• Valentin Polishchuk, Joseph S. B. Mitchell:
  Thick non-crossing paths and minimum-cost flows in polygonal domains. 56-65
  
• Jonathan Backer, David G. Kirkpatrick:
  Finding curvature-constrained paths that avoid polygonal obstacles. 66-73
  
• Yevgeny Schreiber:
  Shortest paths on realistic polyhedra. 74-83
  
• Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang:
  Querying approximate shortest paths in anisotropic regions. 84-91
  

Session 3

• David Eppstein:
  Happy endings for flip graphs. 92-101
  
• Adrian Dumitrescu, Ichiro Suzuki, Pawel Zylinski:
  Offline variants of the "lion and man" problem. 102-111
  
• Ares Ribó Mor, Günter Rote, André Schulz:
  Embedding 3-polytopes on a small grid. 112-118
  

Session 4A: video session

• Frédéric Cazals, Sebastien Loriot:
  Computing the exact arrangement of circles on a sphere, with applications in structural biology: video. 119-120
  
• Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock:
  Visualizing bregman voronoi diagrams. 121-122
  
• Balint Miklos, Joachim Giesen, Mark Pauly:
  Medial axis approximation from inner Voronoi balls: a demo of the Mesecina tool. 123-124
  
• Kevin Buchin, André Schulz:
  Inflating the cube by shrinking. 125-126
  
• Gill Barequet, Alina Shaikhet:
  Heilbronn's triangle problem. 127-128
  
• Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan:
  Kinetic 3D convex hulls via self-adjusting computation. 129-130
  
• Linqiao Zhang, Hazel Everett, Sylvain Lazard, Sue Whitesides:
  Towards an implementation of the 3D visibility skeleton. 131-132
  

Session 4B

• János Pach, Géza Tóth:
  Decomposition of multiple coverings into many parts. 133-137
  
• Saurabh Ray, Nabil H. Mustafa:
  An optimal generalization of the centerpoint theorem, and its extensions. 138-141
  
• Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, Günter Rote:
  There are not too many magic configurations. 142-149
  

Session 5

• Yuanxin Liu, Jack Snoeyink:
  Quadratic and cubic b-splines by generalizing higher-order voronoi diagrams. 150-157
  
• Arno Eigenwillig, Lutz Kettner, Nicola Wolpert:
  Snap rounding of Bézier curves. 158-167
  
• Lilian Buzer:
  Optimal simplification of polygonal chain for rendering. 168-174
  
• Mohammad Ali Abam, Mark de Berg, Peter Hachenberger, Alireza Zarei:
  Streaming algorithms for line simplification. 175-183
  

Session 6

• Gunnar Carlsson, Afra Zomorodian:
  The theory of multidimensional persistence. 184-193
  
• Jean-Daniel Boissonnat, Leonidas J. Guibas, Steve Oudot:
  Manifold reconstruction in arbitrary dimensions using witness complexes. 194-203
  
• Piotr Indyk, Anastasios Sidiropoulos:
  Probabilistic embeddings of bounded genus graphs into planar graphs. 204-209
  
• Mirela Ben-Chen, Craig Gotsman, Camille Wormser:
  Distributed computation of virtual coordinates. 210-219
  

Session 7

• Esther Ezra, János Pach, Micha Sharir:
  On regular vertices on the union of planar objects. 220-226
  
• József Solymosi, Gábor Tardos:
  On the number of k-rich transformations. 227-231
  
• Pankaj K. Agarwal, Roel Apfelbaum, George B. Purdy, Micha Sharir:
  Similar simplices in a d-dimensional point set. 232-238
  
• Saurabh Ray, Nabil H. Mustafa:
  Weak epsilon-nets have basis of size o(1/epsilon log (1/epsilon)) in any dimension. 239-244
  

Session 8A

• Ciprian Borcea, Xavier Goaoc, Sylvain Petitjean:
  Line transversals to disjoint balls. 245-254
  
• Hazel Everett, Sylvain Lazard, Daniel Lazard, Mohab Safey El Din:
  The voronoi diagram of three lines. 255-264
  
• Julien Demouth, Olivier Devillers, Hazel Everett, Marc Glisse, Sylvain Lazard, Raimund Seidel:
  Between umbra and penumbra. 265-274
  

Session 8B

• Darko Dimitrov, Christian Knauer, Klaus Kriegel, Günter Rote:
  New upper bounds on the quality of the PCA bounding boxes in r² and r³. 275-283
  
• Victor Chepoi, Karim Nouioua:
  Pareto envelopes in R³ under l₁ and l_infinity distance functions. 284-293
  
• Pankaj K. Agarwal, Haim Kaplan, Micha Sharir:
  Computing the volume of the union of cubes. 294-301
  

Session 9

• Luis Rademacher:
  Approximating the centroid is hard. 302-305
  
• Hans Raj Tiwary:
  On the hardness of minkowski addition and related operations. 306-309
  
• Thorsten Bernholt, Friedrich Eisenbrand, Thomas Hofmeister:
  A geometric framework for solving subsequence problems in computational biology efficiently. 310-318
  
• Efi Fogel, Dan Halperin, Christophe Weibel:
  On the exact maximum complexity of Minkowski sums of convex polyhedra. 319-326
  

Session 10

• Boris Aronov, Sariel Har-Peled, Micha Sharir:
  On approximate halfspace range counting and relative epsilon-approximations. 327-336
  
• Peyman Afshani, Timothy M. Chan:
  On approximate range counting and depth. 337-343
  
• Yakov Nekrich:
  A data structure for multi-dimensional range reporting. 344-353
  
• Erik D. Demaine, Mihai Patrascu:
  Tight bounds for dynamic convex hull queries (again). 354-363
  

Session 11

• Mohammad Ali Abam, Mark de Berg, Bettina Speckmann:
  Kinetic KD-trees and longest-side KD-trees. 364-372
  
• Liam Roditty:
  Fully dynamic geometric spanners. 373-380
  
• Pankaj K. Agarwal, Sariel Har-Peled, Hai Yu:
  Embeddings of surfaces, curves, and moving points in euclidean space. 381-389