Browsing Congreso de Geometría Computacional (15º. 2013. Sevilla) by Title
Now showing items 120 of 35

A symbolicnumeric dynamic geometry environment for the computation of equidistant curves [Presentation]
(2013)A webbased system that determines point/curve and curve/curve bisectors in a dynamic geometry system in a completely automatic way is presented. The system consists of an interactive drawing canvas where the bisector is ... 
Abstract Voronoi diagrams [Presentation]
(2013)Abstract Voronoi diagrams are a unifying framework that covers many types of concrete Voronoi diagrams. This talk reports on the state of the art, including recent progress. 
An algorithm that constructs irreducible triangulations of oncepunctured surfaces [Presentation]
(2013)A triangulation of a surface is irreducible if there is no edge whose contraction produces another triangulation of the surface. In this work we propose an algorithm that constructs the set of irreducible triangulations ... 
Computing the stretch of an embedded graph [Presentation]
(2013)Let G be a graph embedded in an orientable surface Σ, possibly with edge weights, and denote by len(γ) the length (the number of edges or the sum of the edge weights) of a cycle γ in G. The stretch of a graph embedded on ... 
Continuous surveillance of points by rotating floodlights [Presentation]
(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 ... 
Distance domination, guarding and vertex cover for maximal outerplanar graphs [Presentation]
(2013)In this paper we de ne a distance guarding concept on plane graphs and associate this concept with distance domination and distance vertex cover concepts on triangulation graphs. Furthermore, for any nvertex maximal ... 
Drawing the double circle on a grid of minimum size [Presentation]
(2013)In 1926, Jarník introduced the problem of drawing a convex ngon with vertices having integer coordinates. He constructed such a drawing in the grid [1, c ·n 3/2]2 for some constant c > 0, and showed that this grid size ... 
Empty convex polytopes in random point sets [Presentation]
(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 ... 
Equipartitioning triangles [Presentation]
(2013)An intriguing conjecture of Nandakumar and Ramana Rao is that for every convex body K ⊆ R2, and for any positive integer n, K can be expressed as the union of n convex sets with disjoint interiors and each having the same ... 
Flips in combinatorial pointed pseudotriangulations with face degree at most four [Presentation]
(2013)In this paper we consider the flip operation for combinatorial pointed pseudotriangulations where faces have size 3 or 4, socalled combinatorial 4PPTs. We show that every combinatorial 4PPT is stretchable to a geometric ... 
Guarding the vertices of thin orthogonal polygons is NPhard [Presentation]
(2013)An orthogonal polygon of P is called “thin” if the dual graph of the partition obtained by extending all edges of P towards its interior until they hit the boundary is a tree. We show that the problem of computing a minimum ... 
Improved enumeration of simple topological graphs [Presentation]
(2013)A simple topological graph T = (V (T ), E(T )) is a drawing of a graph in the plane where every two edges have at most one common point (an endpoint or a crossing) and no three edges pass through a single crossing. Topological ... 
Metaheuristic approaches for the minimum dilation triangulation problem [Presentation]
(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. ... 
Monotone crossing number of complete graphs [Presentation]
(2013)In 1958, Hill conjectured that the minimum number of crossings in a drawing of Kn is exactly Z(n) = 1/4 n1/2/2 n−2/2 n−3/2. Generalizing the result by Ábrego et al. for 2page book drawings, we prove this conjecture for ... 
Note on the number of obtuse angles in point sets [Presentation]
(2013)In 1979 Conway, Croft, Erd\H{o}s and Guy proved that every set SS of nn points in general position in the plane determines at least n3/18−O(n2) obtuse angles and also presented a special set of nn points to show the upper ... 
On 4connected geometric graphs [Presentation]
(2013)Given a set S of n points in the plane, in this paper we give a necessary and sometimes sufficient condition to build a 4connected noncrossing geometric graph on S. 
On making a graph crossingcritical [Presentation]
(2013)A graph is crossingcritical if its crossing number decreases when we remove any of its edges. Recently it was proved that if a nonplanar graph G is obtained by adding an edge to a cubic polyhedral (planar 3connected) ... 
On the barrierresilience of arrangements of raysensors [Presentation]
(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 ... 
On the enumeration of permutominoes [Presentation]
(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 ... 
On the nonexistence of kreptile simplices in R3 and R4 [Presentation]
(2013)A ddimensional simplex S is called a kreptile (or a kreptile simplex) if it can be tiled without overlaps by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d=2, triangular ...