21. EWCG 2005: Eindhoven, The Netherlands

Triangulations and Meshing

• Shripad Thite:
  A unified algorithm for adaptive spacetime meshing with nonlocal cone constraints. 1-4
  
• Alper Üngör:
  Quality triangulations made smaller. 5-8
  
• J. Mark Keil, Tzvetalin S. Vassilev:
  The relative neighbourhood graph is a part of every 30°-triangulation. 9-12
  
• Magdalene Grantson, Christos Levcopoulos:
  Bounds on optimally triangulating connected subsets of the minimum weight convex partition. 13-16
  
• Kevin Buchin:
  Incremental construction along space-filling curves. 17-20
  

Spanners

• Jean Cardinal, Sébastien Collette, Stefan Langerman:
  Region counting graphs. 21-24
  
• Sergio Cabello, Bojan Mohar, Arjana Zitnik:
  Homotopic spanners. 25-28
  
• Mohammad Farshi, Panos Giannopoulos, Joachim Gudmundsson:
  Finding the best shortcut in a geometric network. 29-32
  
• Christian Knauer, Wolfgang Mulzer:
  An exclusion region for minimum dilation triangulations. 33-36
  
• Adrian Dumitrescu, Ansgar Grüne, Günter Rote:
  Improved lower bound on the geometric dilation of point sets. 37-40
  

Matching

• Anil Maheshwari, Jiehua Yi:
  On computing Fréchet distance of two paths on a convex polyhedron. 41-44
  
• Helmut Alt, Maike Buchin:
  Semi-computability of the Fréchet distance between surfaces. 45-48
  
• Darko Dimitrov, Christian Knauer, Klaus Kriegel:
  Matching surfaces with characteristic points. 49-51
  
• Oliver Klein, Remco C. Veltkamp:
  Approximation algorithms for the Earth mover's distance under transformations using reference points. 53-56
  
• Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote:
  Matching point sets with respect to the Earth mover's distance. 57-60
  

Combinatorial and Discrete Geometry

• Oswin Aichholzer, Hannes Krasser:
  Abstract order type extension and new results on the rectilinear crossing number. 61-64
  
• Carmen Cortés, Alberto Márquez, Atsuhiro Nakamoto, Jesus Valenzuela:
  Quadrangulations and 2-colorations. 65-68
  
• Lyuba Alboul, Gilberto Echeverria, Marcos A. Rodrigues:
  Discrete curvatures and Gauss maps for polyhedral surfaces. 69-72
  
• Pilar Sabariego, Francisco Santos:
  On the number of facets of three-dimensional Dirichlet stereohedra III: Cubic group. 73-76
  

Pseudo-Triangulations

• Günter Rote, André Schulz:
  A pointed Delaunay pseudo-triangulation of a simple polygon. 77-80
  
• Oswin Aichholzer, Franz Aurenhammer, Clemens Huemer, Hannes Krasser:
  Transforming spanning trees and pseudo-triangulations. 81-84
  
• Franz Aurenhammer, Hannes Krasser:
  Pseudo-tetrahedral complexes. 85-88
  
• Oswin Aichholzer, Clemens Huemer, Sarah Renkl, Bettina Speckmann, Csaba D. Tóth:
  On pseudo-convex decompositions, partitions, and coverings. 89-92
  
• Michael Hoffmann, Csaba D. Tóth:
  Pointed binary encompassing trees: Simple and optimal. 93-96
  

Approximation and Competitive Algorithms

• Narcís Coll, Marta Fort, Joan Antoni Sellarès:
  Approximate multi-visibility map computation. 97-100
  
• Corinne Feremans, Alexander Grigoriev:
  Approximation schemes for the generalized geometric problems with geographic clustering. 101-102
  
• Sariel Har-Peled:
  Approximation algorithm for the L1-fitting circle problem. 103-106
  
• Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen:
  Competitive online searching for a ray in the plane. 107-110
  
• Tom Kamphans, Elmar Langetepe:
  On optimizing multi-sequence functionals for competitive analysis. 111-114
  

Higher-Order Delaunay Triangulations and GIS

• Thierry de Kok, Marc J. van Kreveld, Maarten Löffler:
  Minimizing local minima in terrains with higher-order Delaunay triangulations. 115-118
  
• Manuel Abellanas, Prosenjit Bose, Jesús García, Ferran Hurtado, Mariano Nicolás, Pedro A. Ramos:
  On properties of higher-order Delaunay graphs with applications. 119-122
  
• Henning Meyerhenke:
  Constructing higher-order Voronoi diagrams in parallel. 123-126
  
• Iris Reinbacher, Marc Benkert, Marc J. van Kreveld, Alexander Wolff:
  Delineating boundaries for imprecise regions. 127-130
  
• Farshad Rostamabadi, Mohammad Ghodsi:
  An efficient algorithm for label updating in 2PM model to avoid a moving object. 131-134
  

Implementation Issues and Experimental Research

• René Brandenberg, Thorsten Theobald:
  Exact analysis of optimal configurations in radii computations. 135-138
  
• Peter Hachenberger, Lutz Kettner:
  Boolean operations on 3D selective Nef complexes: Optimized implementation and experiments. 139-142
  
• Galina Pasko, Alexander A. Pasko, Tosiyasu L. Kunii:
  Ternary blending operations. 143-145
  
• Ioannis Z. Emiris, George M. Tzoumas:
  Algebraic study of the Apollonius circle of three ellipses. 147-150
  

Voronoi Diagrams

• Ron Wein, Jur P. van den Berg, Dan Halperin:
  The visibility-Voronoi complex and its applications. 151-154
  
• Robert Görke, Alexander Wolff:
  Constructing the city Voronoi diagram faster. 155-158
  
• Yaron Ostrovsky-Berman:
  Computing transportation Voronoi diagrams in optimal time. 159-162
  
• Imma Boada, Narcís Coll, Narcis Madern, Joan Antoni Sellarès:
  Approximations of 3D generalized Voronoi diagrams. 163-166
  
• Marcin Bienkowski, Valentina Damerow, Friedhelm Meyer auf der Heide, Christian Sohler:
  Average case complexity of Voronoi diagrams of n sites from the unit cube. 167-170
  

Miscellaneous Geometry

• Mohammad Ali Abam, Mark de Berg:
  Lower bounds for kinetic sorting. 171-174
  
• Yaron Ostrovsky-Berman, Leo Joskowicz:
  Uncertainty envelopes. 175-178
  
• José Miguel Díaz-Báñez, Carlos Seara, Joan Antoni Sellarès, Jorge Urrutia, Inmaculada Ventura:
  Covering point sets with two convex objects. 179-182
  
• Sebastian Böcker, Veli Mäkinen:
  Maximum line-pair stabbing problem and its variations. 183-186
  
• Ramtin Khosravi, Mohammad Ghodsi:
  The fastest way to view a query point in simple polygons. 187-190
  

Geometric Networks

• Paz Carmi, Matthew J. Katz:
  The minimum area spanning tree problem. 191-194
  
• Christian Knauer, Étienne Schramm, Andreas Spillner, Alexander Wolff:
  Spanning trees with few crossings in geometric and topological graphs. 195-198
  
• Magdalene Grantson, Henk Meijer, David Rappaport:
  Bi-chromatic minimum spanning trees. 199-202
  
• Marc Benkert, Joachim Gudmundsson, Herman J. Haverkort, Alexander Wolff:
  Constructing interference-minimal networks. 203-206
  
• Emilio Di Giacomo, Giuseppe Liotta:
  A note on simultaneous embedding of planar graphs. 207-210