14th European Workshop on
Computational Geometry

March 25(evening)-26-27, 1998 Barcelona

General Information

The European Workshop on Computational Geometry was organized in 1998 by the UPC Research Group in Computational Geometry, a Research group of the Departament de Matemàtica Aplicada II of the Universitat Politècnica de Catalunya.

The goal of the workshop was to bring together the researchers in Computational Geometry, facilitating -through an informal scheme- the diffusion of their most recent work.

No proceedings will be published but the abstracts will be collected and distributed among the participants at the workshop. A Special Issue of Discrete Applied Mathematics will be devoted to selected papers from contributions presented at the conference. The usual high standards of the Journal will be applied to this selection of papers through a strict and ehorough refereeing process. Guest Editors: F. Hurtado, M. Noy, J. S. B. Mitchell.

CG'97: the 13th European Workshop on Computational Geometry was hold in Würzburg in 1997.
CG'99: the 15th European Workshop on Computational Geometry will be hold in Nice in 1999.


17:00-19:00 Registration
19:00-20:00 INVITED TALK. On the exact query complexity of planar point location. Raimund Seidel.


Session 1. Chair: Joerg-Rudiger Sack

08:50-09:10 A Randomized Parallel Algorithm for Voronoi Diagrams Based on Symmetric Convex Distance Functions. Ulrich Kuhn.
09:10-09:30 An Iterative Algorithm for the Determination of Voronoi Verti ces in Polygonal and Non-Polygonal Domains on the Plane and the Sphere. Francois Anton, Jack Snoeyink, Christopher Gold.
09:30-09:50 An Algorithm for the Dynamic Construction and Maintenance of Additively Weighted Voronoi Diagrams. Darka Mioc, Francois Anton, Christopher Gold.
09:50-10:10 The Bisector with Respect to Different Convex Distance Functions. Christian Icking, Rolf Klein, Lihong Ma.

10:10-10:40 Coffee-break

Session 2. Chair: Manuel Abellanas

10:40-11:00 An Improved Diamond Property for Minimum-Weight Triangulations. R. L. (Scot) Drysdale, Scott McElfresh, Jack Scott Snoeyink.
11:00-11:20 Robust Computation of Euclidean Minimum Spanning Trees. Fabrizio d'Amore, Paolo-Giulio Franciosa, Giuseppe Liotta.
11:20-11:40 Two-Point Euclidean Shortest Path Queries in the Plane. Yi-Jen Chiang, Joseph S. B. Mitchell.
11:40-12:00 An epsilon-Approximation Algorithm for Weighted Shortest Path Queries on Polyhedral Surfaces. Lyudmil Aleksandrov, Mark Lanthier, Anil Maheshwari, Joerg-Rudiger Sack.
12:00-13:00 INVITED TALK. Predicate Arithmetic for Geometric Computing. Jean-Daniel Boissonnat.

13:00-14:30 Lunch

Session 3. Chair: Hazel Everett

14:30-14:50 More Results on Computational Geometry on the Cylinder. Juan- Carlos Dana, Clara-Isabel Grima, Ferran Hurtado, Alberto Marquez.
14:50-15:10 Computing Roundness in Practice. Pedro Ramos.
15:10-15:30 New Algorithmic Tools for Comparing 2D Patterns of Protein Spots. Frank Hoffmann, Klaus Kriegel, Carola Wenk.
15:30-15:50 The 3D Visibility Skeleton. Fredo Durand, George Dretakkis, Claude Puech.
15:50-16:10 Planning the Motion of a Segment in a Polygonal Environment. Ernesto Staffetti.

16:10-16:40 Coffee-break

Session 4. Chair: Rolf Klein

16:40-17:00 Bistellar Flips in Triangulations of Point Configurations. Francisco Santos.
17:00-17:20 Edge Flipping in Triangulations of Surfaces. Carmen Cortes, Ferran Hurtado, Alberto Marquez, Atsuhiro Nakamoto.
17:20-17:40 Applying Delta/Star Reductions for Checking the Spatial Reali zability of Line Drawings. Lluis Ros, Federico Thomas.
17:40-18:00 Computer Drawings of Non-Symmetric Configurations. Marko Boben, Harald Gropp, Tomasz Pisanski.

18:00-18:15 Business meeting


Session 5. Chair: Jack Snoeyink

08:30-08:50 Computing the Combinatorial Structure of Arrangements of Curves Using Polygonal Approximations. Manuela Neagu, Bernard Lacolle.
08:50-09:10 On the Maximal Number of Facets of 3-Dimensional Dirichlet Stereohedra. Daciana Bochis, Francisco Santos.
09:10-09:30 Properties of Arrangement Graphs. Prosenjit Bose, Hazel Everett, Steve Wismath.
09:30-09:50 Generalized Self-Approaching Curves. Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein, Elmar Langetepe, Gunter Rote.
09:50-10:10 Sweeps, Arrangements and Higher Bruhat Orders. Stefan Felsner, Helmut Weil.

10:10-10:30 Coffee-break

Session 6. Chair: Joseph S. B. Mitchell

10:40-11:00 Triangles in Euclidean Arrangements. Stefan Felsner, Klaus Kriegel.
11:00-11:20 Ramsey-Remainder for Convex Sets and the Erdos-Szekeres Theorem. Gyula Karoly.
11:20-11:40 Minimum Convex Partition of a Constrained Point Set. Thomas Fevens, Henk Meijer, David Rappaport.
11:40-12:00 Point-Sets with Few k-Sets. Helmut Alt, Stefan Felsner, Ferran Hurtado, Marc Noy.
12:00-13:00 INVITED TALK. Systems of Segments in the Plane. Janos Pach.

13:00-14:30 Lunch

Session 7. Chair: Claude Puech

14:30-14:50 A Locus Approach to Angle Problems in Computational Geometry. Clara-Isabel Grima, Alberto Marquez, Lidia Ortega.
14:50-15:10 Fast and Simple External-Memory Planar Point-Location. Jan Vahrenhold, Klaus Hinrichs.
15:10-15:30 Implicit Convex Polygons. Francisco Gomez, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristan, Godfried Toussaint.
15:30-15:50 Efficient {0,1}-String Searching Based on Pre-Clustering. Oswin Aichholzer.
15:50-16:10 Separating Objects in the Plane with Strips and Wedges. Ferran Hurtado, Marc Noy, Pedro Ramos, Carlos Seara.

16:10-16:40 Coffee-break

Session 8. Chair: Franz Aurenhammer

16:40-17:00 A Simple Treatment for Degeneracies in Geometric Programs. Toshiyuki Imai.
17:00-17:20 Deciding the Sign Using Floating-Point Arithmetic. Hisamoto Hiyoshi, Hiroshi Sekigawa.
17:20-17:40 Interval Arithmetic Yields Efficient Arithmetic Filters for Computational Geometry. Herve Bronnimann, Christoph Burnikel, Sylvain Pion.

Organizing Committee



Departament de Matemàtica Aplicada II
Pau Gargallo 5
08028 Barcelona

e-mail: geomc@ma2.upc.es

fax: + 34 3 401.72.84

phone: + 34 3 401.69.26

(Last update of this page: April 14, 1998)