European Workshop on Computational Geometry (20th. 2004. Sevilla)
Recent Submissions
 Presentation

Presentation
Unfolding simple chains inside circles
(2004)It is an open problem to determined whether a polygonal chain can be straightened inside a confi ning region if its links ...

Presentation
Distributed ranking methods for geographic information retrieval
(2004)Geographic Information Retrieval is concerned with retrieving documents that are related to some location. This paper ...

Presentation
Triangulations without pointed spanning trees
(2004)Problem 50 in the Open Problems Project asks whether any triangulation on a point set in the plane contains a pointed ...

Presentation
Improved results for the kcentrum straightline location problem
(2004)The kCentrum problem consists in finding a point that minimises the sum of the distances to the k farthest points out of ...

Presentation
New bound for incremental constructing arrangements of curves
(2004)Let A(Γ) be the arrangement induced by a set Γ of n unbounded Jordan curves in the plane that intersect each other in at ...

Presentation
The minimum Manhattan network problem approximations and exact solutions
(2004)A Manhattan p–q path is a geodesic in the Manhattan (or L1) metric that connects p and q, i.e. a staircase path between ...

Presentation
Maximum weight triangulation of a special convex polygon
(2004)In this paper, we investigate the maximum weight triangulation of a special convex polygon, called `semicircled convex polygon'. We prove that the maximum weight triangulation of such a polygon can be found in O(n2) time.
 Presentation

Presentation
Defining discrete Morse functions on infinite surfaces
(2004)We present an algorithm which defines a discrete Morse function in Forman’s sense on an infinite surface including a study of the minimality of this function.

Presentation
Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces
(2004)Given an orthogonal polygon P, let Π(P) be the number of rectangles that result when we partition P by extending the ...
 Presentation
 Presentation
 Presentation

Presentation
A simple and less slow method for counting triangulations and for related problems
(2004)We present a simple dynamic programming based method for counting straightedge triangulations of planar point sets. This ...

Presentation
New lower bounds for the number of straightedge triangulations of a planar point set
(2004)We present new lower bounds on the number of straightedge triangulations that every set of n points in plane must have. These bounds are better than previous bounds in case of sets with either many or few extreme points.

Presentation
Verification of partitions of 2d and 3d objects
(2004)We consider the problems of deciding whether a given collection of polygons (polyhedra resp.) forms (i) a partition or ...

Presentation
Guarding art galleries by guarding witnesses
(2004)Let P be a simple polygon. We de ne a witness set W to be a set of points su h that if any (prospective) guard set G ...

Presentation
On geometric properties of enumerations of axisparallel rectangles
(2004)We show that for any set of nonoverlapping axisparallel rectangles in the plane, there exists a sloping enumeration, ...

Presentation
Balanced intervals of two stes of points on a line or circle
(2004)Let n,m, k, h be positive integers such that 1 ≤ n ≤ m, 1 ≤ k ≤ n and 1 ≤ h ≤ m. Then we give a necessary and sufficient ...