SoCG 24

Conference Program

This version reflects the correction of a error in the talk times of sessions 5A/B.

Except as noted, all presentations will take place in the Tyser Auditorium (Room 1212) in Van Munching Hall, on the campus of the University of Maryland, College Park.

Here is the program in pdf.

                    Sunday, June 8
7:00-9:00pm — Welcome Reception and Registration (Reever's Hall, Rigg's Alumni Center) —

                    Monday, June 9
8:15-9:00 — Registration and Light breakfast —
  Session 1
9:10-9:30 Dynamic Coresets
Timothy M. Chan
9:30-9:50 Optimizing Active Ranges for Consistent Dynamic Map Labeling
Ken Been, Martin Nöllenburg, Sheung-Hung Poon and Alexander Wolff
9:50-10:10 Maximum Thick Paths in Static and Dynamic Environments
Esther Arkin, Joseph Mitchell and Valentin Polishchuk
10:10-10:30 Circular Partitions with Applications to Visualization and Embeddings
Krzysztof Onak and Anastasios Sidiropoulos
10:30-11:00 — Coffee break —
11:00–12:00 Invited Talk
Delaunay Triangulations of Polyhedral Surfaces, a Discrete Laplace-Beltrami Operator and Applications
Alexander Bobenko
Technische Universität Berlin
12:00-2:00 — Lunch —
  Session 2A (Tyser Auditorium) Session 2B (Room 1330)
2:00-2:20 Tighter Bounds for Random Projections of Manifolds
Ken Clarkson
The Complexity of the Outer Face in Arrangements of Random Segments
Noga Alon, Dan Halperin, Oren Nechushtan and Micha Sharir
2:25-2:45 Markov Convexity and Local Rigidity of Distorted Metrics
Manor Mendel and Assaf Naor
On s-intersecting Curves and Related Problems
Sarit Buzaglo, Ron Holzman and Rom Pinchasi
2:50-3:10 Diameters, Centers, and Approximating Trees of δ-hyperbolic Geodesic Spaces and Graphs
Victor Chepoi, Feodor Dragan, Bertrand Estellon, Michel Habib and Yann Vaxes
On Levels in Arrangements of Curves, III: Further Improvements
Timothy M. Chan
3:10-3:40 — Coffee break —
  Session 3
3:40-4:00 A (Slightly) Faster Algorithm for Klee's Measure Problem
Timothy M. Chan
4:00-4:20 Walking Your Dog in the Woods in Polynomial Time
Erin Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus and Shripad Thite
4:20-4:40 Hinged Dissections Exist
Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine and Scott D. Kominers
4:40-5:00 Helly-type Theorems for Approximate Covering
Julien Demouth, Olivier Devillers, Marc Glisse and Xavier Goaoc
5:10 — Business Meeting (Tyser Auditorium) —

                    Tuesday, June 10
8:15-9:00 — Registration and Light breakfast —
  Session 4
9:00-9:20 I/O Efficient Algorithms for Computing Contour Lines on a Terrain
Pankaj Agarwal, Lars Arge, Thomas Mølhave and Bardia Sadri
9:20-9:40 External Memory Planar Point Location with Logarithmic Updates
Lars Arge, Gerth Stølting Brodal and S. Srinivasa Rao
9:40-10:00 Self-Improving Algorithms for Delaunay Triangulations
Kenneth L. Clarkson and C. Seshadhri
10:00-10:20 Markov Incremental Constructions
Bernard Chazelle and Wolfgang Mulzer
10:20-10:50 — Coffee break —
  Session 5A (Tyser Auditorium) Session 5B (Room 1330)
10:50-11:10 Exact Geometric-Topological Analysis of Algebraic Surfaces
Eric Berberich, Michael Kerber and Michael Sagraloff
On the Complexity of Checking Self-duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism
Hans Raj Tiwary and Khaled Elbassioni
11:15-11:35 Predicates for Line Transversals to Lines and Line Segments in Three-dimensional Space
Olivier Devillers, Marc Glisse and Sylvain Lazard
New Existence Proofs for ε-Nets
Evangelia Pyrga and Saurabh Ray
11:40-12:00 Robust Construction of the Three-dimensional Flow Complex
Frederic Cazals, Aditya Parameswaran and Sylvain Pion
Extremal Problems on Triangle Areas in Two and Three Dimensions
Adrian Dumitrescu, Micha Sharir and Csaba Toth
12:00-2:00 — Lunch —
  Session 6: Video and Multimedia Presentations
2:00-2:10 Arrangements of Geodesic Arcs on the Sphere
Efi Fogel, Ophir Setter and Dan Halperin
2:10-2:20 DelPSC: A Delaunay Mesher for Piecewise Smooth Complexes
Joshua Levine and Tamal Dey
2:20-2:30 On the Computation of 3D Periodic Triangulations
Manuel Caroli and Monique Teillaud
2:30-2:40 Visualizing and Exploring Planar Algebraic Arrangements - A Web Application
Pavel Emeliyanenko and Michael Kerber
2:40-2:50 Analyzing Rigidity with Pebble Games
Audrey Lee, Ileana Streinu and Louis Theran
2:50-3:00 Minkowski Sums of Rotating Convex Polyhedra
Jyh-Ming Lien
3:00-3:10 Routing a Maximum Number of Disks through a Scene of Moving Obstacles
Joodong Kim, Joseph S.B. Mitchell, Valentin Polishchuk and Arto Vihavainen
3:10-3:40 — Coffee break —
  Session 7
3:40-4:00 Towards Persistence-Based Reconstruction in Euclidean Spaces
Frederic Chazal and Steve Oudot
4:00-4:20 Reeb Spaces of Piecewise Linear Mappings
Herbert Edelsbrunner, John Harer and Amit Patel
4:20-4:40 Testing Contractibility in Planar Rips Complexes
Erin Chambers, Jeff Erickson and Pratik Worah
4:40-5:00 Approximating the Pathway Axis and the Persistence Diagram of a Collection of Balls in 3-Space
Eitan Yaffe and Dan Halperin
6:30 — Conference Banquet (University Golf Course Clubhouse) —

                    Wednesday, June 11
8:15-9:00 — Registration and Light breakfast —
  Session 8
9:00-9:20 Locally Uniform Anisotropic Meshing
Jean-Daniel Boissonnat, Camille Wormser and Mariette Yvinec
9:20-9:40 Discrete Laplace Operator on Meshed Surfaces
Misha Belkin, Jian Sun and Yusu Wang
9:40-10:00 Untangling Triangulations through Local Explorations
Pankaj Agarwal, Bardia Sadri and Hai Yu
10:00-10:20 Delaunay Triangulations of Imprecise Points in Linear Time after Preprocessing
Maarten Löffler and Jack Snoeyink
10:20-10:50 — Coffee break —
10:50–11:50 Invited Talk
Geometry is Everywhere, Part XLVII: Metrics, Nets, Dimensions, and Measures
Kenneth L. Clarkson
IBM Almaden Research Center
11:50-2:00 — Lunch —
  Session 9A (Tyser Auditorium) Session 9B (Room 1330)
2:00-2:20 A Simple and Efficient Kinetic Spanner
Mohammad Ali Abam, Mark de Berg and Joachim Gudmundsson
Fast Enumeration Algorithms for Non-crossing Geometric Graphs
Naoki Katoh and Shin-ichi Tanigawa
2:25-2:45 Schnyder Woods for Higher Genus Triangulated Surfaces
Luca Castelli Aleardi, Eric Fusy and Thomas Lewiner
Polychromatic Colorings of Plane Graphs
Noga Alon, Robert Berke, Maike Buchin, Kevin Buchin, Peter Csorba, Saswata Shannigrahi, Bettina Speckmann and Philipp Zumstein
2:50-3:10 Embedding and Similarity Search for Point Sets under Translation
Minkyoung Cho and David Mount
Coloring Kk-free Intersection Graphs of Geometric Objects in the Plane
Jacob Fox and Janos Pach
3:10-3:40 — Coffee break —
  Session 10
3:40-4:00 Consistent Digital Rays
Jinhee Chun, Matias Korman, Martin Nöllenburg and Takeshi Tokuyama
4:00-4:20 Combinatorial Genericity and Minimal Rigidity
Ileana Streinu and Louis Theran
4:20-4:40 Improved Upper Bounds on the Crossing Number
Vida Dujmovic, Ken-ichi Kawarabayashi, Bojan Mohar and David R. Wood
4:40-5:00 Intersecting Convex Sets by Rays
Rado Fulek, Andreas Holmsen and János Pach
5:00 — Conference Ends —

-   SoCG08 Home   -