20th European Workshop on Computational Geometry. 

March 24-26, 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)


3D realization of two triangulations of a convex polygon

S. Bereg

A certified conflict locator for the incremental maintenance of the Delaunay graph of semi-algebraic sets

F. Anton

A completion of hypotheses method for 3D-geometry. 3D-extensions of Ceva and Menelaus theorems

E. Roanes-Macías, E. Roanes-Lozano

A quadratic distance bound on sliding between crossing-free 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

Farthest-point 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 1-corner corridor

J.M. Díaz-Bañ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. Ebbers-Baumann, 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 k-centrum straight-line 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 pseudo-triangulations

J. Gudmundsson, C. Levcopoulos

New bound for incremental constructing arrangements of curves

M. Abellanas, A. Calatayud, J. García-López

New lower bounds for the number of straight-edge 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 axis-parallel 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 pseudo-triangulations of certain point sets

O. Aichholzer, D. Orden, F. Santos, B. Speckmann

Optimal spanners for axis-aligned 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 NP-hard

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

Quadratic-time, linear-space algorithms for generating orthogonal polygons with a given number of vertices

A. Tomas, A. Bajuelos

Region inter-visibility 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

Space-efficient geometric divide-and-conquer 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íaz-Bañ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