European Workshop on Computational Geometry (20th. 2004. Sevilla): Recent submissions
Now showing items 2140 of 56

Region intervisibility in terrains [Presentation]
(2004)A polyhedral terrain is the image of a piecewise linear continuous function de ned over the triangles of a triangulation in the xy plane. Given a terrain with n vertices, two simplyconnected regions (subsets of the ... 
On fencing problems [Presentation]
(2004)Fencing problems deal with the bisection of a convex body in a way that some geometric measures are optimized. We study bisections of planar bounded convex sets by straight line cuts and also bisections by hyperplane cuts ... 
Computing the Fréchet distance between piecewise smooth curves [Presentation]
(2004)We consider the Fréchet distance between two curves which are given as a sequence of m+n curved pieces. If these pieces are sufficiently wellehaved, we can compute the Fréchet distance in O(mn log(mn)) time. The ... 
Finding a door along a wall with an error afflicted robot [Presentation]
(2004)We consider the problem of finding a door in a wall with a blind robot, that does not know the distance to the door or whether the door is located left hand or right hand to its start point. This problem can be solved with ... 
Geometric data structures for multihierarchical XML tagging of manuscripts [Presentation]
(2004)This paper shows an application of computational geometry methods to the preparation of imagebased digital library editions. We present a formalism for describing nonhierarachical markup of manuscripts in terms of ... 
Lower bounds for the polygon exploration problem [Presentation]
(2004)We improve the best known lower bound for the polygon exploration problem from 1.2071 to 1.2825. 
Pointed encompassing trees [Presentation]
(2004)It is shown that for any set of disjoint line segments in the plane there exists a pointed binary encompassing tree, that is, a spanning tree on the segment endpoints that contains all input segments, has maximal degree ... 
Competitive search ratio of graphs and polygons [Presentation]
(2004)We consider the problem of searching for a goal in an unknown environment, which may be a graph or a polygonal environment. The search ratio is the worstcase ratio before the goal is found while moving along some search ... 
Geometric dilation of closed planar curves: a new lower bound [Presentation]
(2004)Given any simple closed curve C in the Euclidean plane, let w and D denote the minimal and the maximal caliper distances of C, correspondingly. We show that any such curve C has a geometric dilation of at least arcsin( ... 
On the number of pseudotriangulations of certain point sets [Presentation]
(2004)We compute the exact number of pseudotriangulations for two prominent point sets, namely the socalled double circle and the double chain. We also derive a new asymptotic lower bound for the maximal number of pseudotriangulations ... 
Similarity search in semialgebraic pattern spaces [Presentation]
(2004)We describe a general technique to construct data structures for similarity search in semialgebraic pattern spaces. These spaces capture most known combinations of geometric patterns (e.g., point sets, polygons, polygonal ... 
Computing the convex hull of disks using only their chirotope [Presentation]
(2004)We show that the convex hull of a collection of n pairwise disjoint disks in the plane is computable in O(n log n) time using only the chirotope of the collection of disks. The method relies mainly on the development of ... 
Optimizing a 2D function satisfying unimodality properties [Presentation]
(2004) 
Point set stratification and minimum weight structures [Presentation]
(2004)Three different concepts of depth in a point set are considered and compared: Convex depth, location depth and Delaunay depth. As a notion of weight is naturally associated to each depth definition, we also present results ... 
Optimal spanners for axisaligned rectangles [Presentation]
(2004) 
Smoothed number of extreme points under uniform noise [Presentation]
(2004)We analyze the maximal expected number of extreme points of a point set P in Rd that is slightly perturbed by random noise. We assume that each point in P is uniformly distributed in an axisaligned hypercube of side ... 
On relative isodiametric inequalities [Presentation]
(2004)We consider subdivisions of convex bodies G in two subsets E and G\E. We obtain several inequalities comparing the relative volume 1) with the minimum relative diameter and 2) with the maximum relative diameter. In the ... 
A completion of hypotheses method for 3Dgeometry. 3Dextensions of Ceva and Menelaus theorems [Presentation]
(2004)A method that automates hypotheses completion in 3DGeometry is presented. It consists of three processes: defi ning the geometric objects in the confi guration; determining the hypothesis conditions of the confi ... 
Finding planar regions in a terrain [Presentation]
(2004)We consider the problem of computing large connected regions in a triangulated terrain of size n for which the normals of the triangles deviate by at most some small fixed angle. In previous work an exact nearquadratic ... 
Minimum weight pseudotriangulations [Presentation]
(2004)We consider the problem of computing a minimum weight pseudotriangulation of a set S of n points in the plane. We first present an O(n log n)time algorithm that produces a pseudotriangulation of weight O(wt(M(S))· log ...