banner about

socg2010 banner
26th Annual Symposium on Computational Geometry June 13th-16th, 2010 at Snowbird, Utah.


This year's Local Arrangements Chairs are Valerio Pascucci and Suresh Venkatasubramanian.
The Program Committee Chair is David Kirkpatrick.

The Twenty-sixth Annual Symposium on Computational Geometry will be held at Snowbird, Utah. We invite submissions of high-quality papers, videos, and multimedia presentations describing original research addressing computational problems in a geometric setting, in particular their algorithmic solutions, implementation issues, applications, and mathematical foundations.

The topics of the Symposium reflect the rich diversity of research interests in computational geometry. They are intended to highlight both the depth and scope of computational geometry, and to invite fruitful interactions with other disciplines. Topics of interest include, but are not limited to:

  • design, analysis, and implementation of geometric algorithms and data structures; lower bounds on the computational complexity of geometric problems;
  • mathematical, numerical, and algebraic issues arising in the formulation, analysis, implementation, and experimental evaluation of geometric algorithms and heuristics; discrete and combinatorial geometry; computational topology;
  • novel algorithmic applications of geometry in computer graphics, geometric modeling, computer-aided design and manufacturing, scientific computing, geographic information systems, database systems, robotics, computational biology, machine learning, sensor networks, medical imaging, combinatorial optimization, statistical analysis, discrete differential geometry, theoretical computer science, graph drawing, pure mathematics, and other fields.
The conference is organized in coorperation with ACM SIGACT and SIGGRAPH


Committees

Program Committee

  • Hee-Kap Ahn (POSTECH, Korea)
  • Nina Amenta (University of California, Davis, USA)
  • Tetsuo Asano (JAIST, Japan)
  • Sergey Bereg (University of Texas at Dallas, USA)
  • Therese Biedl (University of Waterloo, Canada)
  • Robert Bridson (University of British Columbia, Canada)
  • Erin Chambers (Saint Louis University, USA)
  • Hazel Everett (University Nancy 2, France)
  • Sandor Fekete (Braunschweig University of Technology, Germany)
  • Efi Fogel (Tel Aviv University, Israel)
  • David Kirkpatrick, Chair (University of British Columbia, Canada)
  • Valentin Polishchuk (Helsinki Institute for Information Technology, Finland)
  • Raimund Seidel (Saarland University, Germany)
  • Bettina Speckmann (TU Eindhoven, The Netherlands)
  • Csaba Toth (University of Calgary, Canada)
  • Chee Yap (Courant Institute, NYU, USA)

Video and Multimedia Presentation Program Committee

  • Tamal Dey (Ohio State University)
  • David Eppstein (UC Irvine)
  • Jie Gao (Stony Brook)
  • David Gu (Stony Brook)
  • George Hart (Stony Brook)
  • Joe Mitchell, Chair (Stony Brook)
  • Jonathan Shewchuk (UC Berkeley)
  • Monique Teillaud (INRIA Sophia Antipolis - Mediterranae)

SOCG Steering Committee (2009-2012)

  • Jack Snoeyink, Chair (University of North Carolina)
  • Mark de Berg, Secretary (TU Eindhoven)
  • Joe Mitchell (SUNY Stony Brook)
  • Guenter Rote (FU Berlin)
  • Monique Teillaud (INRIA Sophia Antipolis - Mediterranae)


Program

Monday June 14

Session 1
9:00am - 10:20am
  • Timothy M. Chan. "Optimal Partition Trees"
  • Tobias Christ, Dömötör Pálvölgyi and Miloš Stojakovic. "Consistent digital line segments"
  • Bernard Chazelle. "The Geometry of Flocking"
  • Sunil Arya, David Mount and Jian Xia. "Tight Lower Bounds for Halfspace Range Searching"
Session 2
10:50am - 12:00pm
Invited Talk I
  • Helmut Pottmann. "Discrete Geometric Structures for Architecture"
Session 3
1:30pm - 2:30pm
  • Mark de Berg. "Better Bounds on the Union Complexity of Locally Fat Objects"
  • Marc Glisse and Sylvain Lazard. "On the complexity of the sets of free lines and free line segments among balls in three dimensions"
  • Natan Rubin. "Lines Avoiding Balls in Three Dimensions Revisited"
Session 4
3:00pm - 4:20pm
  • Sergio Cabello and Bojan Mohar. "Adding one edge to planar graphs makes crossing number hard"
  • Joachim Gudmundsson and Pat Morin. "Planar Visibility: Testing and Counting"
  • Pankaj K. Agarwal, Rinat Ben Avraham and Micha Sharir. "The 2-Center Problem in Three Dimensions"
  • Ken-ichi Kawarabayashi, Stephan Kreutzer and Bojan Mohar. "Linkless and flat embeddings in 3-space and the Unknot problem"
Session 5
4:30pm - 5:30pm
Video presentations
  • Gur Harary and Ayellet Tal. "Visualizing 3D Euler Spirals"
  • Dmitry N. Krasnoshchekov, Valentin Polishchuk, and Arto Vihavainen. "Eating Ice-Cream with Colander"
  • Harish Doraiswamy, Aneesh Sood, and Vijay Natarajan. "Constructing Reeb Graphs using Cylinder Maps"
  • Adrian Dumitrescu and Evan Hilscher. "Convexification of polygons"
  • Stephen J. Guy, Jur van den Berg, Ming C. Lin, and Dinesh Manocha. "Geometric Methods for Multi-Agent Collision Avoidance"
5:30pm Business Meeting

Tuesday June 15

Session 6A
9:00am - 10:15am
  • Bernard Chazelle. "A Geometric Approach to Collective Motion"
  • Pankaj K. Agarwal, Jie Gao, Leonidas Guibas, Haim Kaplan, Vladlen Koltun, Natan Rubin and Micha Sharir. "Kinetic Stable Delaunay Graphs"
  • Kaim Kaplan, Natan Rubin and Micha Sharir. "A Kinetic Triangulation Scheme For Moving Points in The Plane"
Session 6B
9:00am - 10:15am
  • Sergio Cabello, Éric Colin de Verdiére and Francis Lazarus. "Output-sensitive algorithm for the edge-width of an embedded graph"
  • Sergio Cabello, Éric Colin de Verdiére and Francis Lazarus. "Finding Shortest Non-Trivial Cycles in Directed Graphs on Surfaces"
  • Tamal Dey, Jian Sun and Yusu Wang. "Approximating loops in a shortest homology basis from point data"
Session 7A
10:45am - 12: 00
  • Florian Berger and Rolf Klein. "A Traveller's Problem"
  • Joseph Mitchell. "A Constant-Factor Approximation Algorithm for TSP with Neighborhoods in the Plane"
  • Mohammad Ali Abam and Sariel Har-Peled. "New Constructions of SSPDs and their Applications"
Session 7B
10:45am - 12:00pm
  • Benjamin A. Burton. "The complexity of the normal surface solution space"
  • Keiko Imai, Akitoshi Kawamura, Jiri Matousek, Daniel Reem and Takeshi Tokuyama. "Distance k-sectors exist"
  • Akitoshi Kawamura, Jiri Matousek and Takeshi Tokuyama. "Zone diagrams in Euclidean spaces and in other normed spaces"
12:00pm - 3:00pm Lunch & Hike
Session 8A
3:00pm - 4:20pm
  • Karl Bringmann. "Klee's Measure Problem on Fat Boxes in Time $O(n^{(d+2)/3})$"
  • Pankaj K. Agarwal. "An Improved Algorithm for Computing the Volume of the Union of Cubes"
  • Peyman Afshani, Lars Arge and Kasper Dalgaard Larsen. "Orthogonal Range Reporting: Query lower bounds, optimal structures in 3-d, and higher-dimensional improvements"
  • David Mount and Eunhui Park. "A Dynamic Data Structure for Approximate Range Searching"
Session 8B
3:00pm - 4:20pm
  • Afra Zomorodian. "The Tidy Set: A Minimal Simplicial Set for Computing Homology of Clique Complexes"
  • William Harvey, Yusu Wang and Rephael Wenger. "A Randomized $O(m\log m)$ Time Algorithm for Computing Reeb Graphs of Arbitrary Simplicial Complexes"
  • Don Sheehy, Benoit Hudson, Gary Miller and Steve Oudot. "Topological Inference via Meshing"
  • Omid Amini, Jean-Daniel Boissonnat and Pooran Memari. "Geometric Tomography With Topological Guarantees"
Session 9A
4:50pm - 5:50pm
  • Micha Sharir, Adam Sheffer and Emo Welzl. "On Degrees in Random Triangulations"
  • Eryk Kopczynski, Igor Pak and Piotr Przytycki. "Acute triangulations of polyhedra and the space $\Re^n$"
  • Umut Acar, Andrew Cotter, Benoit Hudson and Duru Türkoglu. "Dynamic Well-Spaced Point Sets"
Session 9B
4:50pm - 5:50pm
  • Jean-Daniel Boissonnat and Arijit Ghosh. "Manifold Reconstruction using Tangential Delaunay Complexes"
  • Dominique Attali and André Lieutier. "Optimal reconstruction might be hard"
  • Dominique Attali and Andre Lieutier. "Reconstructing shapes with guarantees by unions of convex sets"
6:00pm Banquet

Wednesday June 16

Session 10
9:00am - 10:20am
  • Abdul Basit, Nabil Mustafa, Saurabh Ray and Sarfraz Raza. "Improving the first selection lemma in $\mathbb{R}3$"
  • Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Tillmann Miltzow, Rom Pinchasi, Torsten Ueckerdt and Ran Ziv. "Points with Large Quadrant-Depth"
  • Anne Driemel, Sariel Har-Peled and Carola Wenk. "Approximating the Frechet Distance for Realistic Curves in Near Linear Time"
  • Pankaj Agarwal, Boris Aronov, Marc van Kreveld, Maarten Löffler and Rodrigo Silveira. "Computing Similarity between Piecewise-Linear Functions"
Session 11
10:50am - 12:00pm
Invited Talk II
  • Cláudio T. Silva. Title TBA
Session 12
1:30pm - 2:30pm
  • David Millman and Jack Snoeyink. "Computing Planar Voronoi Diagrams in Double Precision: An Example of Degree-driven Algorithm Analysis"
  • Gur Harary and Ayellet Tal. "3D Euler Spirals for 3D Curve Completion"
  • Lars Arge, Morten Revsbaek and Norbert Zeh. "I/O-efficient computation of water flow across a terrain"
Session 13
3:00pm - 4:00pm
  • György Elekes and Micha Sharir. "Incidences in Three Dimensions and Distinct Distances in the Plane"
  • Janos Pach, Andrew Suk and Miroslav Treml. "Tangencies between families of disjoint regions in the plane"
  • David Eppstein and Elena Mumford. "Steinitz Theorems for Orthogonal Polyhedra"