|
Contributed talks are 15 minutes plus 3 minutes time for
questions and answers plus 2 minutes for synchronizing with the
parallel session.
The sessions will take place in room E23 (1A, 2A, ...) and
room E04/05 (1B, 2B, ...). All invited talks and "Fast Forward"
sessions will take place in room E23.
The proceedings are available as a PDF file.
|
Sunday, March 21, 2010
|
|
18:00 - 20:00
|
Registration (Foyer)
|
|
18:00 - 20:00
|
Welcome Reception (Foyer)
|
|
Monday, March 22, 2010
|
|
08:00 - 12:00
|
Registration (Foyer)
|
|
09:00 - 09:15
|
Opening
Welcome Address (Walter Grünzweig, Vice President, TU Dortmund)
Welcome Address (Peter Buchholz, Dean, Department of
Computer Science, TU Dortmund)
|
|
09:15 - 10:15
|
Invited Talk
Point Samples for Surface Representation and Geometry Processing
Markus Gross, ETH Zurich and Disney Research Zurich
|
|
10:15 - 10:25
|
Fast Forward for Sessions 1A&1B
|
|
10:25 - 10:55
|
Coffee Break
|
|
10:55 - 12:15
|
|
Session 1A
|
Session 1B
|
Certifying curve-reconstruction algorithms
Asish Mukhopadhyay, Harshit Rathod, Chong Wang, and Bryan St. Amour
|
From invariants to predicates: example of line transversals to lines
Guillaume Batog
|
Polygonal Reconstruction from Approximate Offsets
Eric Berberich, Dan Halperin, Michael Kerber, and Roza Pogalnikova
|
Regular triangulations and resultant polytopes
Ioannis Emiris, Vissarion Fisikopoulos, and Christos Konaxis
|
Approximating the Frechet Distance for Realistic Curves in Near Linear Time
Anne Driemel, Sariel Har-Peled, and Carola Wenk
|
Combinatorial Proof for fast Pivoting in K-matrix Linear Complementarity
Jan Foniok, Komei Fukuda, and Lorenz Klaus
|
Recursive tilings and space-filling curves with little fragmentation
Herman Haverkort
|
Embedding into the rectilinear plane in optimal O(n2) time
Victor Chepoi, Nicolas Catusse, and Yann Vaxes
|
|
|
12:15 - 12:25
|
Fast Forward for Sessions 2A&2B
|
|
12:25 - 13:55
|
Lunch (attendees on their own)
|
|
13:55 - 15:15
|
|
Session 2A
|
Session 2B
|
Largest Inscribed Rectangles in Convex Polygons
Christian Knauer, Lena Schlipf, Jens M. Schmidt, and Hans Raj Tiwary
|
Arc Triangulations
Oswin Aichholzer, Franz Aurenhammer, Katerina Cech Dobiasova, Bert Juettler, and Wolfgang Aigner
|
The Class Cover Problem with Boxes
Sergey Bereg, Sergio Cabello, José-Miguel Díaz-Báñez, Pablo Pérez-Lantero, Carlos Seara, and Inmaculada Ventura Molina
|
Triangulating a System of Disks
Daniel Peterseim
|
Approximation algorithms for free-label maximization
Mark de Berg and Dirk H.P. Gerrits
|
Even and quasi-even triangulations of point sets in the plane
Isabel Fernández Delgado, Clara Isabel Grima Ruiz, Alberto Márquez Pérez, Atsuhiro Nakamoto, Rafael Robles Arias, and Jesús Valenzuela Muñoz
|
Hardness of discrepancy and related problems parameterized by the dimension
Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner
|
Even Triangulation of Planar Set of Points with Steiner Points
Victor Alvarez
|
|
|
15:15 - 15:25
|
Fast Forward for Sessions 3A&3B
|
|
15:25 - 15:55
|
Coffee Break
|
|
15:55 - 17:15
|
|
Session 3A
|
Session 3B
|
Robot Swarms for Exploration and Triangulation of Unknown Environments
Sándor Fekete, Tom Kamphans, Alexander Kröller, and Christiane Schmidt
|
Connecting Obstacles in Vertex-Disjoint Paths
Marwan Al-Jubeh, Gill Barequet, Mashhood Ishaque, Diane Souvaine, Csaba Toth, and Andrew Winslow
|
Hide-and-Seek: A Linear Time Algorithm for Polygon Walk Problems
Atlas F. Cook IV, Chenglin Fan, and Jun Luo
|
The geodesic diameter of polygonal domains
Sang Won Bae, Matias Korman, and Yoshio Okamoto
|
Straight Skeletons and their Relation to Triangulations
Stefan Huber and Martin Held
|
A Traveller's Problem
Florian Berger and Rolf Klein
|
3-Colorability of Pseudo-Triangulations
Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Clemens Huemer, Alexander Pilz, and Birgit Vogtenhuber
|
The time-optimal helicopter trajectory is a circle segment
Andre Berger, Alexander Grigoriev, and Natalya Usotskaya
|
|
|
17:15 - 18:00
|
Business meeting
|
|
18:00 - 19:00
|
Currywurst reception
|
|
Tuesday, March 23, 2010
|
|
08:00 - 12:00
|
Registration (Room 239)
|
|
09:00 - 10:00
|
Invited Talk
Touching Points
János Pach, EPFL Lausanne and Rényi Institute Budapest
|
|
10:00 - 10:10
|
Fast Forward for Sessions 4A&4B
|
|
10:10 - 10:40
|
Coffee Break
|
|
10:40 - 12:00
|
|
Session 4A
|
Session 4B
|
A new separation theorem with geometric applications
Farhad Shahrokhi
|
The Tidy Set: A Minimal Simplicial Set for Computing Homology of Clique Complexes
Afra Zomorodian
|
Steinitz Theorems for Orthogonal Polyhedra
David Eppstein and Elena Mumford
|
Certified Computation of planar Morse-Smale Complexes
Amit Chattopadhyay, Sijbo Holtman, and Gert Vegter
|
The edge rotation graph
Javier Cano, Mayra Corvera Espinoza, José Miguel Díaz-Báñez, Joel Espinosa Longi, Clemens Huemer, and Jorge Urrutia
|
Geometric realization of a triangulation on the Klein bottle with one face removed
Atsuhiro Nakamoto and Shoichi Tsuchiya
|
On the Diameter of a Geometric Johnson Type Graph
Crevel Bautista-Santiago, Javier Cano, Ruy Fabila-Monroy, David Flores-Peñaloza, Hernán González-Aguilar, Dolores Lara, Eliseo Sarmiento, and Jorge Urrutia
|
Delaunay Triangulations of Point Sets in Closed Euclidean d-Manifolds
Manuel Caroli and Monique Teillaud
|
|
|
12:00 - 13:45
|
Lunch (attendees on their own)
|
|
13:45 - 14:45
|
Invited Talk
Instance-Optimal Geometric Algorithms
Timothy M. Chan, University of Waterloo
|
|
14:45 - 14:55
|
Fast Forward for Sessions 5A&5B
|
|
14:55 - 15:30
|
Coffee Break
|
|
15:30 - 16:50
|
|
Session 5A
|
Session 5B
|
A fast and easy-to-implement algorithm for the Minimal Translational Distance (MTD) of boxes
Kai Werth and Elmar Schömer
|
Order types of segments in floorplan partitions
Andrei Asinowski, Gill Barequet, Toufik Mansour, and Ron Y. Pinter
|
Real-Time Offset Surfaces
Andreas von Dziegielewski, Rainer Erbes, and Elmar Schömer
|
On Rectilinear Partitions with Minimum Stabbing Number
Mark de Berg and AmirAli Khosravi
|
How to cope with undesired side effects of symbolic perturbation
Shuhei Takahashi and Kokichi Sugihara
|
Computing the depth of an arrangement of axis-aligned rectangles in parallel
Helmut Alt and Ludmila Scharf
|
Snap Rounding on the Sphere
Boris Kozorovitzky and Dan Halperin
|
Evacuation of rectilinear polygons
Sándor Fekete, Chris Gray, and Alexander Kröller
|
|
|
16:50 - 17:00
|
Fast Forward for Sessions 6A&6B
|
|
19:00 - 22:00
|
Conference Dinner at Der Lennhof
|
|
Wednesday, March 24, 2010
|
|
09:00 - 10:20
|
|
Session 6A
|
Session 6B
|
Removing Local Extrema from Imprecise Terrains
Chris Gray, Maarten Löffler, and Rodrigo Silveira
|
Hiding in the Crowd: Asymptotic Bounds on Blocking Sets
Natasa Jovanovic, Jan Korst, Zharko Aleksovski and Radivoje Jovanovic
|
Circles with Independent and Dependent Uncertainties
Yonatan Myers and Leo Joskowicz
|
Blocking Coloured Point Sets
Greg Aloupis, Brad Ballinger, Sebastien Collette, Stefan Langerman, Attila Por, and David Wood.
|
Finding Structures on Imprecise Points
Mark de Berg, Elena Mumford, and Marcel Roeloffzen
|
Guarding 1.5D Terrains with Demands
Khaled Elbassioni, Domagoj Matijevic and Domagoj Severdija
|
Convex Hull Of Imprecise Points Modeled By Segments
Ahmad Javad, Ali Mohades, Mansoor Davoodi, and Farnaz Sheikhi
|
On Widest Empty Wedges
Yan Mayster, Riquelmi Cardona, and Mario Lopez
|
|
|
10:20 - 10:30
|
Fast Forward for Sessions 7A&7B
|
|
10:30 - 11:00
|
Coffee Break
|
|
11:00 - 12:20
|
|
Session 7A
|
Session 7B
|
How Alexander the Great Brought the Greeks Together while Inflicting Minimal Damage to the Barbarians
Mark de Berg, Dirk Gerrits, Amirali Khosravi, Ignaz Rutter, Constantinos Tsirogiannis, and Alexander Wolff
|
Nearest-neighbor queries with well-spaced points
Chris Gray
|
Locating an Obnoxious Line Through a Set of Weighted Points
Yan Mayster, Mohammed Al-Bow, Catherine Durso and Mario Lopez
|
Approximate Nearest Neighbor Queries among Parallel Segments
Ioannis Emiris, Theocharis Malamatos, and Elias Tsigaridas
|
Separability of Point Sets by k-Level Linear Classification Trees
Esther M. Arkin, Delia Garijo, Alberto Márquez, Joseph S. B. Mitchell, and Carlos Seara
|
Proximity Graphs inside Large Weighted Graphs
Bernardo Abrego, Ruy Fabila, Silvia Fernandez-Merchant, David Flores, Ferran Hurtado, Henk Meijer, Vera Sacristan, and Maria Saumell
|
One-Reporting Queries
Saladi Rahul and Rajan K.S.
|
A Reactive-Agent Based Approach for a Facility Location Problem Using Dynamic Additively Weighted Voronoi Diagram
Arman Didandeh, Mehdi Khosravian, and Bahram Sadeghi Bigham
|
|
|
12:20 - 12:30
|
Fast Forward for Sessions 8A&8B
|
|
12:30 - 14:00
|
Lunch (attendees on their own)
|
|
14:00 - 15:20
|
|
Session 8A
|
Session 8B
|
Fitting Flats to Points with Outliers
Guilherme da Fonseca
|
2-Factor Approximation Algorithm for Computing Maximum Independent Set of a Unit Disk Graph
Sudeshna Kolay, Subhas Nandy, and Susmita Sur-Kolay.
|
Partial Least-Squares Point Matching under Translations
Günter Rote
|
Planar Hop Spanners for Unit Disk Graphs
Victor Chepoi, Nicolas Catusse and Yann Vaxes
|
Towards Non-Uniform Geometric Matchings
Fabian Stehn, Christian Knauer, and Klaus Kriegel
|
Memoryless Routing in Convex Subdivisions: Random Walks are Optimal
Dan Chen, Luc Devroye, Vida Dujmovič, and Pat Morin
|
Computing the discrete Fréchet distance with imprecise input
Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, and Antoine Vigneron
|
Coding and Counting Arrangements of Pseudolines
Stefan Felsner and Pavel Valtr
|
|
|
15:20 - 15:30
|
Fast Forward for Session 9
|
|
15:30 - 16:00
|
Coffee Break
|
|
16:00 - 17:20
|
|
Session 9
|
On the complexity of the edge guarding problem
Vicente H. F. Batista, Fábio Protti and Fernando L. B. Ribeiro
|
Computing the visibility area between two simple polygons in linear time
Rainer Penninger, Elmar Langetepe, and Jan Tulke
|
Partial Visibility Polygon with Semi-Transparent Objects
Mostafa Nouri Baygi and Mohammad Ghodsi
|
Visibility Polygons in the Presence of a Mirror Edge
Bahram Kouhestani, Mohammad Asgaripour, Salma Sadat Mahdavi, Arash Nouri, and Ali Mohades
|
|
|
17:20 - 17:30
|
Closing remarks
|
|
Program
