25th European Workshop on Computational Geometry

March 16-18, 2009

ULB, Brussels, Belgium

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