Buscar
Mostrando ítems 1-10 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 edges incident to reflex vertices towards INT(P). In Tomás, A. P., Bajuelos, A. L., Marques, F.: ...
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 guards W, then it is guaranteed that G guards P . We show that not all polygons admit a nite witness ...
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 bisections of planar bounded convex sets by straight line cuts and also bisections by hyperplane cuts ...
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 method can be adapted to solve related problems such as nding the best triangulation of a point set ...
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 the triangles deviate by at most some small fixed angle. In previous work an exact near-quadratic ...
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. The search ratio is the worst-case ratio before the goal is found while moving along some search ...
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 algebraic equations or inequalities (semi-algebraic sets). The Voronoi diagram of a set of sites is a ...
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 condition for every configuration with n red points and m blue points on a line or circle to have an ...