Buscar
Mostrando ítems 41-50 de 56
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 condition for every configuration with n red points and m blue points on a line or circle to have an ...
Ponencia
Approximate distance oracles for graphs with dense clusters
(2004)
Let G be a graph containing N disjoint t-spanners that are inter-connected with M edges. We present an algorithm that constructs a data structure of size O(M2 + n log n) that answers (1 + ε)-approximate shortest path queries ...
Ponencia
3D realization of two triangulations of a onvex polygon
(2004)
We study the problem of construction of a convex 3-polytope whose (i) shadow boundary has n vertices and (ii) two hulls, upper and lower, are isomorphic to two given triangulations of a convex n-gon. Barnette [℄ D. W. ...
Ponencia
Minimum number of different distances defined by a finite number of points
(2004)
We study the minimum number of different distances defined by a finite number of points in the following cases: a) we consider metrics different from the euclidean distance in the plane, b) we consider the euclidean distance ...
Ponencia
Lower bounds for the polygon exploration problem
(2004)
We improve the best known lower bound for the polygon exploration problem from 1.2071 to 1.2825.
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 two trees in TS can be transformed into each other by O(n2) local and constant-size edge slide ...
Ponencia
Computing the Fréchet distance between piecewise smooth curves
(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 well-ehaved, we can compute the Fréchet distance in O(mn log(mn)) time. The ...
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 in the xy- plane. Given a terrain with n vertices, two simply-connected regions (subsets of the ...
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 are not allowed to cross. In this paper we propose a special case: whether a polygonal chain can be ...