socg2010_splash
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"