Buscar
Mostrando ítems 1-10 de 56
Ponencia
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
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 is a planar straight-line embedding of G such that the vertices V are embedded onto the points P is ...
Ponencia
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
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 p and q. Given a set of points P in the plane, a Manhattan network is a set of axis-parallel line ...
Ponencia
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
On geodesic and monophonic convexity
(2004)
In this paper we deal with two types of graph convexities, which are the most natural path convexities in a graph and which are defined by a system P of paths in a connected graph G: the geodesic convexity (also called ...
Ponencia
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
On relative isodiametric inequalities
(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 ...
Ponencia
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
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 spanning tree as a subgraph. We provide a counterexample. As a consequence we show that there ...
Ponencia
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
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
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
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
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
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
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
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
![Con acceso al texto completo Icon](/themes/idUS//images/acceso/opened_access.png)
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 depth. As a notion of weight is naturally associated to each depth definition, we also present results ...