20th European Workshop on Computational Geometry.March 2426, 2004 Seville, Spain 
Invited Talks (abstracts available from Preliminary Program)  Authors  
Combinatorial Geometry for TV Audiences  Jin Akiyama  
Some Stamps on Combinatorial Geometry  Ferran Hurtado  
Structure in Visibility Graphs  David Rappaport  
Accepted Papers (papers available from Preliminary Program) 
Authors 

3D realization of two triangulations of a convex polygon 
S. Bereg 

A certified conflict locator for the incremental maintenance of the Delaunay graph of semialgebraic sets 
F. Anton 

A completion of hypotheses method for 3Dgeometry. 3Dextensions of Ceva and Menelaus theorems 
E. RoanesMacías, E. RoanesLozano 

A quadratic distance bound on sliding between crossingfree spanning trees 
O.Aichholzer, K. Reinhardt 

A simple and less slow method for counting triangulations and for related problems 
S. Ray, R. Seidel 

Approximate Distance Oracles for Graphs with Dense Clusters 
M. Andersson, J. Gudmunsson, C. Levcopoulos 

Approximate Range searching using binary space partitions 
M. de Berg, M. Streppel 

Balanced intervals of two stes of points on a line or circle 
A. Kaneko, M. Kano 

Competitive search ratio of graphs and poligons 
R. Fleischer, T. Kamphans, R. Klein, E. Langetepe 

Computing the convex hull of disks using only their chirotope 
L. Habert, M. Pocchiola 

Computing the Fréchet distance between piecewise smooth curves 
G. Rote 

Computing the Hausdorff distance between curved objets 
H. Alt, L. Scharf 

Curvature criteria to fit curves to discrete data 
L. Alboul, G. Echeverria, M. Rodrigues 

Defining discrete Morse functions on infinite surfaces 
R. Ayala, L. Fernandez, J. Vilches 

Distributed ranking methods for geographic information retrieval 
M. van Kreveld, I. Reinbacher, A. Arampatzis, R. van Zwol 

Farthestpoint queries with geometric and combinatorial constraints 
O. Daescu, N. Mi, C. Shin, A. Wolff 

Finding a door along a wall with an error afflicted robot 
T. Kamphans, E. Langetepe 

Finding a widest empty 1corner corridor 
J.M. DíazBañez, M.A. López, J.A. Sellarès 

Finding planar regions in a terrain 
S. Funke, T. Malamatos, R. Ray 

Geometric data structures for multihierarchical XML tagging of manuscripts 
J. Jaromczyk, N. Moore 

Geometric dilation of closed planar curves: A new lower bound 
A. EbbersBaumann, A. Grüne, R. Klein 

Guarding art galleries by guarding witnesses 
K. Chawa, B. Jo, C. Knauer, E. Moet, R. van Oostrum, C. Shin 

Improved results for the kcentrum straightline location problem 
A. Lozano, J. Mesa, F. Plastria 

Lower bounds for the polygon exploration problem 
R. Hagius, C. Icking, E. Langetepe 

Maximizing the area of overlap of two unions of disks under rigid motion 
M. de Berg, S. Cabello, P. Giannopoulos, C. Knauer, R. van Oostrum, R. Veltkamp 

Maximum weight triangulation of a special convex polygon 
J. Qian, C. Wang 

Minimum number of different distances defined by a finite number of points 
A. Albujer, S. Segura Gomis 

Minimun weight pseudotriangulations 
J. Gudmundsson, C. Levcopoulos 

New bound for incremental constructing arrangements of curves 
M. Abellanas, A. Calatayud, J. GarcíaLópez 

New lower bounds for the number of straightedge triangulations of a planar point set 
P. McCabe, R. Seidel 

On fencing problems 
C. Miori, C. Peri, S. Segura Gomis 

On geodesic and monophonic convexity 
C. Hernando, M. Mora, I. Pelayo, C. Seara 

On geometric properties of enumerations of axisparallel rectangles 
K. Vyatkina 

On rectangular cartograms 
M. van Kreveld, B. Speckmann 

On relative isodiametric inequalities 
A. Cerdán, C. Miori, S. Segura Gomis 

On the number of pseudotriangulations of certain point sets 
O. Aichholzer, D. Orden, F. Santos, B. Speckmann 

Optimal spanners for axisaligned rectangles 
T. Asano, M. de Berg, O. Cheong, H. Everett, H. Haverkort, N. Katoh, A. Wolff 

Optimizing a 2D function satisfying unimodality properties 
E. Demaine, S. Langerman 

Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces 
A. Bajuelos, A. Tomás, F. Marques 

Planar embeddability of the vertices of a graph using a fixed point set is NPhard 
S. Cabello 

Point set stratification and minimum weight structures 
M. Abellanas, M. Claverol, F. Hurtado 

Pointed encompassing trees 
M. Hoffmann, B. Sechmann, C. Tóth 

Quadratictime, linearspace algorithms for generating orthogonal polygons with a given number of vertices 
A. Tomas, A. Bajuelos 

Region intervisibility in terrains 
M. van Kreveld, E. Moet, R. van Oostrum 

Similarity search in semialgebraic pattern spaces 
C. Knauer 

Smoothed number of extreme points under uniform noise 
V. Damerow, C. Sohler 

Spaceefficient geometric divideandconquer algorithms 
P. Bose, A. Maheshwari, P. Morin J. Morrison, M. Smid, J. Vahrenhold 

Straight line skeleton in linear time, topologically equivalent to the medial axis 
M. Tanase, R. Veltkamp 

The minimum Manhattan network problem approximations and exact solutions 
M. Benkert, T. Shirabe, A. Wolff 

The siphon problem 
J.M. DíazBañez, C. Seara, I. Ventura 

Triangulations without pointed spanning trees 
O. Aichholzer, C. Huemer, H. Krasser 

Two Optimization problems with floodlights 
A. Spillner 

Unfolding simple chains inside circles 
M. Eskandari, A. Mohades 

Using symmetry evaluation to improve robotic manipulation performance 
P.Sanz, S. Dabic, R. Marin 

Verification of partitions of 2D and 3D objets 
L. Palios 

Warping cubes: better triangles from marching cubes 
L. Tzeng 