Listar European Workshop on Computational Geometry (20th. 2004. Sevilla) por título
Mostrando ítems 39-56 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
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 ...
-
Ponencia
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 ...
-
Ponencia
Pointed encompassing trees
(2004)It is shown that for any set of disjoint line segments in the plane there exists a pointed binary encompassing tree, that ...
- Ponencia
-
Ponencia
Region inter-visibility in terrains
(2004)A polyhedral terrain is the image of a piecewise linear continuous function de ned over the triangles of a triangulation ...
-
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
Smoothed number of extreme points under uniform noise
(2004)We analyze the maximal expected number of extreme points of a point set P in Rd that is slightly perturbed by random noise. ...
-
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
-
Ponencia
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 ...
-
Ponencia
The siphon problem
(2004)An α-siphon is the locus of points in the plane that are at the same distance ǫ from a polygonal chain consisting of two ...
-
Ponencia
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 ...
- Ponencia
-
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
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 ...
- Ponencia