Listar European Workshop on Computational Geometry (20th. 2004. Sevilla) por fecha de publicación
Mostrando ítems 1-20 de 56
-
Ponencia
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 ...
-
Ponencia
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 ...
-
Ponencia
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 ...
-
Ponencia
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 ...
-
Ponencia
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 ...
-
Ponencia
Competitive search ratio of graphs and polygons
(2004)We consider the problem of searching for a goal in an unknown environment, which may be a graph or a polygonal environment. ...
-
Ponencia
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.
-
Ponencia
A certified conflict locator for the incremental maintenance of the Delaunay graph of semi-algebraic sets
(2004)Most of the curves and surfaces encountered in geometric modelling are defined as the set of solutions of a system of ...
- Ponencia
-
Ponencia
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 ...
-
Ponencia
Space-efficient geometric divide-and-conquer algorithms
(2004)We present an approach to simulate divide-and-conquer algorithms in a space-efficient way, and illustrate it by giving ...
-
Ponencia
A quadratic distance bound on sliding between crossing-free spanning trees
(2004)Let S be a set of n points in the plane and let TS be the set of all crossing-free spanning trees of S. We show that any ...
-
Ponencia
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.
-
Ponencia
Distributed ranking methods for geographic information retrieval
(2004)Geographic Information Retrieval is concerned with retrieving documents that are related to some location. This paper ...
-
Ponencia
Computing the convex hull of disks using only their chirotope
(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 ...
-
Ponencia
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 ...
- Ponencia
-
Ponencia
Similarity search in semialgebraic pattern spaces
(2004)We describe a general technique to construct data structures for similarity search in semialgebraic pattern spaces. These ...
-
Ponencia
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 ...
-
Ponencia
A completion of hypotheses method for 3D-geometry. 3D-extensions of Ceva and Menelaus theorems
(2004)A method that automates hypotheses completion in 3D-Geometry is presented. It consists of three processes: defi ning the ...