Browsing European Workshop on Computational Geometry (20th. 2004. Sevilla) by Issue Date
Now showing items 1-20 of 56
-
Presentation
Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
(2004)Let G = (V, E) be a graph with n vertices and let P be a set of n points in the plane. We show that deciding whether there ...
-
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
On geodesic and monophonic convexity
(2004)In this paper we deal with two types of graph convexities, which are the most natural path convexities in a graph and which ...
-
Presentation
On relative isodiametric inequalities
(2004)We consider subdivisions of convex bodies G in two subsets E and G\E. We obtain several inequalities comparing the relative ...
-
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
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
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
On fencing problems
(2004)Fencing problems deal with the bisection of a convex body in a way that some geometric measures are optimized. We study ...
-
Presentation
Finding planar regions in a terrain
(2004)We consider the problem of computing large connected regions in a triangulated terrain of size n for which the normals of ...
-
Presentation
Point set stratification and minimum weight structures
(2004)Three different concepts of depth in a point set are considered and compared: Convex depth, location depth and Delaunay ...
-
Presentation
Maximizing the area of overlap of two unions of disks under rigid motion
(2004)Let A and B be two sets of n resp. m (m ≥ n) disjoint unit disks in the plane. We consider the problem of finding a rigid ...
- Presentation
-
Presentation
Minimum weight pseudo-triangulations
(2004)We consider the problem of computing a minimum weight pseudo-triangulation of a set S of n points in the plane. We first ...
-
Presentation
Geometric data structures for multihierarchical XML tagging of manuscripts
(2004)This paper shows an application of computational geometry methods to the preparation of image-based digital library editions. ...
-
Presentation
Similarity search in semialgebraic pattern spaces
(2004)We describe a general technique to construct data structures for similarity search in semialgebraic pattern spaces. These ...
- Presentation
-
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
-
Presentation
On rectangular cartograms
(2004)A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that ...
-
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.