Buscar
Mostrando ítems 1-10 de 31
Ponencia
Metaheuristic approaches for the minimum dilation triangulation problem
(2013)
We focus on the development of approximated algorithms to find high quality triangulations of minimum dilation because the complexity status of the Minimum Dilation Triangulation problem for a general point set is unknown. ...
Ponencia
Monotone crossing number of complete graphs
(2013)
In 1958, Hill conjectured that the minimum number of crossings in a drawing of Kn is exactly Z(n) = 1/4 n-1/2/2 n−2/2 n−3/2. Generalizing the result by Ábrego et al. for 2-page book drawings, we prove this conjecture for ...
Ponencia
Continuous surveillance of points by rotating floodlights
(2013)
Let P and F be sets of n ≥ 2 and m ≥ 2 points in the plane, respectively, so that P∪F is in general position. We study the problem of finding the minimum angle α ∈ [2π/m, 2π] such that one can install at each point of F a ...
Ponencia
Flips in combinatorial pointed pseudo-triangulations with face degree at most four
(2013)
In this paper we consider the flip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs. We show that every combinatorial 4-PPT is stretchable to a geometric ...
Ponencia
Empty convex polytopes in random point sets
(2013)
Given a set P of points in Rd, a convex hole (alternatively, empty convex polytope) of P is a convex polytope with vertices in P, containing no points of P in its interior. Let R be a bounded convex region in Rd. We show ...
Ponencia
Three location tapas calling for CG sauce
(2013)
Based on some recent modelling considerations in location theory we call for study of three CG constructs of Voronoi type that seem not to have been studied much before.
Ponencia
Stabbing simplices of point sets with k-flats
(2013)
Let S be a set of n points in Rd in general position. A set H of k-flats is called an mk-stabber of S if the relative interior of any m-simplex with vertices in S is intersected by at least one element of H. In this paper ...
Ponencia
On the barrier-resilience of arrangements of ray-sensors
(2013)
Given an arrangement A of n sensors and two points s and t in the plane, the barrier resilience of A with respect to s and t is the minimum number of sensors whose removal permits a path from s to t such that the path ...
Ponencia
On the enumeration of permutominoes
(2013)
Although the exact counting and enumeration of polyominoes remain challenging open problems, several positive results were achieved for special classes of polyominoes. We give an algorithm for direct enumeration of ...
Ponencia
On three parameters of invisibility graphs
(2013)
The invisibility graph I(X) of a set X ⊆ Rd is a (possibly infinite) graph whose vertices are the points of X and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding ...