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

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. ... 
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 ... 
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 ... 
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. 
Parallel constrained Delaunay triangulation [Presentation]
(2013)In this paper we propose a new GPU method able to compute the 2D constrained Delaunay triangulation of a planar straight line graph consisting of points and segments. The method is based on an incremental insertion, taking ... 
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 ... 
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 ... 
Simulated annealing applied to the MWPT problem [Presentation]
(2013)The Minimum Weight PseudoTriangulation (MWPT) problem is suspected to be NPhard. We show here how Simulated Annealing (SA) can be applied for obtaining approximate solutions to the optimal ones. To do that, we applied ... 
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 ... 
Stackable tessellations [Presentation]
(2013)We introduce a class of solids that can be constructed gluing stackable pieces, which has been proven to have advantages in architectural construction. We derive a necessary condition for a solid to belong to this class. ... 
SensoGraph: Using proximity graphs for sensory analysis [Presentation]
(2013)Sensory evaluation of foods is as important as chemical, physical or microbiological examinations, being specially relevant in food industries. Classical methods can be long and costly, making them less suitable for certain ... 
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 ... 
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) ... 
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 ... 
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 ... 
Phase transitions in the RamseyTurán theory [Presentation]
(2013)Let f(n) be a function and L be a graph. Denote by RT(n, L, f(n)) the maximum number of edges of an Lfree graph on n vertices with independence number less than f(n). Erdos and Sós asked if RT (n, K5, c√ n) = o (n2) for ... 
Recent developments on the crossing number of the complete graph [Presentation]
(2013) 
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 ... 
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. 
Some results on open edge guarding of polygons [Presentation]
(2013)This paper focuses on a variation of the Art Gallery problem that considers open edge guards. The “open” prefix means the endpoints of an edge where a guard is are not taken into account for visibility purposes. This paper ...