European Workshop on Computational Geometry (20th. 2004. Sevilla): Recent submissions
Now showing items 1-20 of 56
- 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 k-centrum straight-line location problem
(2004)The k-Centrum 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 `semi-circled 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 straight-edge triangulations of planar point sets. This ...
-
Presentation
New lower bounds for the number of straight-edge triangulations of a planar point set
(2004)We present new lower bounds on the number of straight-edge 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 axis-parallel rectangles
(2004)We show that for any set of non-overlapping axis-parallel 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 ...