25th European Workshop on Computational Geometry

March 16-18, 2009

ULB, Brussels, Belgium

Call for Papers

The reception will happen in the "Grand hall" of the A building (entrance through Avenue Franklin Roosevelt).

The conference itself will happen in the "Dupréel" and "Baugniet" rooms of the S building (entrance through Avenue Jeanne).

  Sunday, March 15th
18:00 Reception
  Monday, March 16th
8:45 Registration
09:15 Invited talk 1: Luc Devroye, McGill U.
10:15 Coffee Break
  Session 1A Session 1B
10:45 Witness Gabriel graphs
Boris Aronov, Muriel Dulieu and Ferran Hurtado
Maintaining Exactly the Convex Hull of Points Moving along Circles
Paul-Georg Becker, Elvir Büyükbayrak and Nicola Wolpert
11:00 Measuring the Similarity of Geometric Graphs
Otfried Cheong, Joachim Gudmundsson, Hyo-Sil Kim, Daria Schymura and Fabian Stehn
k-Means Motion Clustering
Frank Hellweg and Christian Sohler
11:15 Spanner Properties of pi/2-Angle Yao Graphs
Mirela Damian, Nawar Molla and Val Pinciu
The Maximum Box Problem for Moving Points on the Plane
Pablo Pérez-Lantero, Sergey Bereg, José-Miguel Díaz-Báñez and Inmaculada Ventura
11:30 Wiener Index and Diameter of a Planar Graph in Subquadratic Time
Christian Wulff-Nilsen
Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions
Fabian Stehn, Christian Knauer and Klaus Kriegel
11:45 Tailored Bregman Ball Trees for Effective Nearest Neighbors
Frank Nielsen, Paolo Piro and Michel Barlaud
Computing Push Plans for Disk-Shaped Robots
Dirk H.P. Gerrits and Mark de Berg
12:00 Lunch Break
  Session 2A Session 2B
14:00 Complexity of pleats folding
Tsuyoshi Ito, Masashi Kiyomi, Shinji Imahori and Ryuhei Uehara
Point Distance Problems with Dependent Uncertainties
Yonatan Myers and Leo Joskowicz
14:15 Modelling rigid origami with Quaternions
Weina Wu and Zhong You
An Improved Algorithm for Inserting a Highway in a City Metric Based on Minimization of Quasiconvex Functions
Matias Korman and Takeshi Tokuyama
14:30 Source Unfoldings of Convex Polyhedra with respect to Certain Closed Polygonal Curves
Jin-ichi Itoh, Joseph O'Rourke and Costin Vilcu
Frechet Distance in Weighted Regions
Yam Ki Cheung and Ovidiu Daescu
14:45 Locked Thick Chains
Erik D. Demaine, Martin L. Demaine, Stefan Langerman and Jérôme Vervier
Safe Routes on a Street Graph with Minimum Power Transmission Range
Manuel Abellanas, Antonio Leslie Bajuelos and Ines Matos
15:00 Fitting a Point Set by Small Monotone Orthogonal Chains
José-Miguel Díaz-Báñez, Mario A. López, Carlos Seara and Inmaculada Ventura
Line Segment Facility Location in Weighted Regions
Yam Ki Cheung and Ovidiu Daescu
15:15 Coffee Break
  Session 3A Session 3B
15:45 Improvement of the Method for Making Quad Meshes through Temperature Contours
Minori Okabe, Shinji Imahori and Kokichi Sugihara
Two-Convex Polygons
Oswin Aichholzer, Franz Aurenhammer, Ferran Hurtado, Pedro Ramos and Jorge Urrutia
16:00 From Mesh Parameterization to Geodesic Distance Estimation
Joachim Giard and Benoît Macq
Geometric Measures on Imprecise Points in Higher Dimensions
Heinrich Kruger and Maarten Löffler
16:15 Certified Meshing of RBF-based Isosurfaces
Gert Vegter, Simon Plantinga and Amit Chattopadhyay
Some Regularity Measures for Convex Polygons
Ferran Hurtado, Vera Sacristán and Maria Saumell
16:30 Low-resolution Surface Mapping: a Topological and Geometrical Approach
Jean-Marie Favreau and Vincent Barra
Inducing n-gon of an arrangement of lines
Ludmila Scharf and Marc Scherfenberg
16:45 Matching Terrains under a Linear Transformation
Pankaj Agarwal, Boris Aronov, Marc van Kreveld, Maarten Löffler and Rodrigo Silveira
Large bichromatic point sets admit empty monochromatic 4-gons
Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado and Birgit Vogtenhuber
17:00 Cutting an Organic Surface
Jean-Marie Favreau and Vincent Barra
  Tuesday, March 17th
09:15 Invited talk 2: Prosenjit Bose, Carleton U.
10:15 Coffee Break
  Session 4A Session 4B
10:45 Lower and upper bounds on the number of empty cylinders and ellipsoids
Oswin Aicholzer, Franz Aurenhammer, Olivier Devillers, Thomas Hackl, Monique Teillaud and Birgit Vogtenhuber
Guarding Orthogonal Art Galleries with Sliding Cameras
Matthew J. Katz and Gila Morgenstern
11:00 Efficient Enumeration of All Pseudoline Arrangements
Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara and Kento Nakada
Inspecting a Set of Strips Optimally
Elmar Langetepe and Tom Kamphans
11:15 On the Number of Crossing-Free Partitions in the Plane
Andreas Razen and Emo Welzl
Modem Illumination of Monotone Polygons
Oswin Aichholzer, Ruy Fabila-Monroy, David Flores-Peñaloza, Thomas Hackl, Clemens Huemer, Jorge Urrutia and Birgit Vogtenhuber
11:30 Counting the Number of Embeddings of Minimally Rigid Graphs
Ioannis Emiris and Antonios Varvitsiotis
Low-Cost Tours for Nearsighted Watchmen with Discrete Vision
Sandor Fekete and Christiane Schmidt
11:45 Reconstructing Points on a Circle from Labeled Distances
David Bremner, Erik D. Demaine, Perouz Taslakian and Godfried Toussaint
Natural Wireless Localization is NP-hard
Tobias Christ, Michael Hoffmann and Yoshio Okamoto
12:00 Lunch Break
  Session 5A Session 5B
14:00 Shortest Path Problems on a Polyhedral Surface
Atlas F. Cook IV and Carola Wenk
Visibility Maps of Realistic Terrains have Linear Smoothed Complexity
Mark de Berg, Herman Haverkort and Constantinos P. Tsirogiannis
14:15 Conflict-Free Coloring Made Stronger
Shakhar Smorodinsky, Roi Krakovski and Elad Horev
Planar Visibility Counting
Matthias Fischer, Matthias Hilbig, Claudius Jähn, Friedhelm Meyer auf der Heide and Martin Ziegler
14:30 Two Applications of Point Matching
Günter Rote
On the Limitations of Combinatorial Visibilities
Yann Disser, Davide Bilo, Matus Mihalak, Subhash Suri, Elias Vicari and Peter Widmayer
14:45 Distance k-Sectors and Zone Diagrams
Keiko Imai, Akitoshi Kawamura, Jirí Matousek, Yu Muramatsu and Takeshi Tokuyama
Dynamic Segment Visibility
Mojtaba Nouri Bygi and Mohammad Ghodsi
15:00 Finding a Minimum Stretch of a Function
Kevin Buchin, Maike Buchin, Marc van Kreveld and Jun Luo
Computing Direct Shadows Cast by Convex Polyhedra
Julien Demouth and Xavier Goaoc
15:15 Coffee Break
  Session 6A Session 6B
15:45 Straight Walk Algorithm Modification for Point Location in a Triangulation
Roman Soukal and Ivana Kolingerová
Homotopic Rectilinear Routing with Few Links and Thick Edges
Kevin Verbeek and Bettina Speckmann
16:00 Every 4-connected Möbius triangulation is geometrically realizable
Atsuhiro Nakamoto and Shoichi Tsuchiya
Area-Universal Rectangular Layouts
David Eppstein, Elena Mumford, Bettina Speckmann and Kevin Verbeek
16:15 Multi-pseudotriangulations
Vincent Pilaud and Michel Pocchiola
Constructability of Trip-lets
Jeroen Keiren, Freek van Walderveen and Alexander Wolff
16:30 Fast Delaunay Triangulation for Converging Point Relocation Sequences
Pedro M. M. de Castro and Olivier Devillers
Finding Perfect Auto-partition is NP-hard
Mark de Berg and AmirAli Khosravi
16:45 Linear-Time Delaunay Triangulations Simplified
Kevin Buchin and Wolfgang Mulzer
Tight Spans and Coarsest Subdivisions of Convex Polytopes
Sven Herrmann
17:00 2D Delaunay mesh generation with area/aspect-ratio constraints
Narcís Coll, Marité Guerrieri and J. Antoni Sellarès
17:15 Business Meeting
  Banquet starting at 19:30
Les salons de l'Atalaïde
  Wednesday, March 18th
09:15 Invited talk 3: Mark Overmars, Utrecht U.
10:15 Coffee Break
  Session 7A Session 7B
10:45 Stabbers of line segments in the plane
Merce Claverol, Delia Garijo, Clara Grima, Alberto Marquez and Carlos Seara
Robust Voronoi-based Curvature and Feature estimation
Quentin Merigot, Maks Ovsjanikov and Leonidas Guibas
11:00 Online Square Packing
Sandor Fekete, Nils Schweer and Tom Kamphans
Inverted Ball as Boundary-constraint for Voronoi Diagrams of 3D Spheres
Martin Manák and Ivana Kolingerová
11:15 Square and Rectangle Covering with Outliers
Hee-Kap Ahn, Sang Won Bae, Matias Korman, Iris Reinbacher, Wanbin Son and Sang-Sub Kim
Divide-and-Conquer for Voronoi Diagrams Revisited
Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Thomas Hackl, Bert Juettler, Elisabeth Pilgerstorfer and Margot Rabl
11:30 Identifying Well-Covered Minimal Bounding Rectangles in 2D Point Data
Marc van Kreveld, Thijs van Lankveld and Remco Veltkamp
The Voronoi diagram of three arbitrary lines in R^3
Hazel Everett, Christian Gillot, Daniel Lazard, Sylvain Lazard and Marc Pouget
11:45 Fixed-parameter tractability and lower bounds for stabbing problems
Panos Giannopoulos, Christian Knauer, Günter Rote and Daniel Werner
Voronoi Diagram in the Klein model using Finsler Geometry
Abolghasem Laleh, Ali Mohades, Zahra Nilforoushan and Morteza Mir Mohammad Rezaii
12:00 Lunch Break
  Session 8A Session 8B
14:00 A Practice-Minded Approach to Computing Motorcycle Graphs
Martin Held and Stefan Huber
On the Optimality of Spiral Search
Elmar Langetepe
14:15 Robust Extraction of the Medial Axes of 3D Objects
Kazutoshi Kan and Kokichi Sugihara
Computing Maximal Islands
Crevel Bautista-Santiago, José-Miguel Díaz-Báñez, Dolores Lara, Pablo Pérez-Lantero, Jorge Urrutia and Inmaculada Ventura
14:30 Continued Work on the Computation of an Exact Arrangement of Quadrics
Michael Hemmer, Sebastian Limbach and Elmar Schömer
On complexity of the mixed volume of parallelograms
Leonid Gurvits
14:45 Exact Construction of Minimum-Width Annulus of Disks in the Plane
Ophir Setter and Dan Halperin
Cache-Oblivious Construction of a Well-Separated Pair Decomposition
Fabian Gieseke and Jan Vahrenhold
15:00 Generic implementation of a modular GCD over Algebraic Extension Fields
Michael Hemmer and Dominik Hülse
Computer Aided Design System for Escher-Like Tilings
Hiroshi Koizumi and Kokichi Sugihara
15:15 Exact Delaunay graph of smooth convex pseudo-circles
Ioannis Z. Emiris, Elias Tsigaridas and George M. Tzoumas