Now showing items 1-20 of 35

    • IconMetaheuristic approaches for the minimum dilation triangulation problem  [Presentation]

      Dorzán, María Gisela; Leguizamón, Mario Guillermo; Mezura Montes, Efrén; Hernández Peñalver, Gregorio (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. ...
    • IconOn the enumeration of permutominoes  [Presentation]

      Nunes Gomes Tomás, Ana Paula (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 ...
    • IconAn algorithm that constructs irreducible triangulations of once-punctured surfaces  [Presentation]

      Chávez de Diego, María José; Lawrecenko, Serge; Portillo Fernández, José Ramón; Villar Liñán, María Trinidad (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 ...
    • IconAbstract Voronoi diagrams  [Presentation]

      Klein, Rolf (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.
    • IconParallel constrained Delaunay triangulation  [Presentation]

      Coll Arnau, Narcís; Guerrieri Basualdo, María Ethel (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 ...
    • IconOn the nonexistence of k-reptile simplices in R3 and R4  [Presentation]

      Kynčl, Jan; Safernova, Zuzana (2013)
      A d-dimensional simplex S is called a k-reptile (or a k-reptile 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 ...
    • IconOn the barrier-resilience of arrangements of ray-sensors  [Presentation]

      Kirkpatrick, David; Yang, Boting; Zilles, Sandra (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 ...
    • IconSimulated annealing applied to the MWPT problem  [Presentation]

      Gagliardi, Edilma Olinda; Leguizamón, Mario Guillermo; Hernández Peñalver, Gregorio (2013)
      The Minimum Weight Pseudo-Triangulation (MWPT) problem is suspected to be NP-hard. We show here how Simulated Annealing (SA) can be applied for obtaining approximate solutions to the optimal ones. To do that, we applied ...
    • IconImproved enumeration of simple topological graphs  [Presentation]

      Kynčl, Jan (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 ...
    • IconStackable tessellations  [Presentation]

      Enrique Monzo, Lluís; Jaume Deyà, Rafel (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. ...
    • IconSensoGraph: Using proximity graphs for sensory analysis  [Presentation]

      Miguel, David N. de; Orden Martín, David; Fernández Fernández, Encarnación; Rodríguez Nogales, José Manuel; Vila Crespo, Josefina (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 ...
    • IconDrawing the double circle on a grid of minimum size  [Presentation]

      Bereg, Sergey; Fabila Monroy, Ruy; Flores Peñaloza, David; Lopez, Mario A.; Pérez Lantero, Pablo (2013)
      In 1926, Jarník introduced the problem of drawing a convex n-gon 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 ...
    • IconOn making a graph crossing-critical  [Presentation]

      Hernández Vélez, César Israel; Leaños Macías, Jesús (2013)
      A graph is crossing-critical if its crossing number decreases when we remove any of its edges. Recently it was proved that if a non-planar graph G is obtained by adding an edge to a cubic polyhedral (planar 3-connected) ...
    • IconContinuous surveillance of points by rotating floodlights  [Presentation]

      Bereg, Sergey; Díaz Báñez, José Miguel; Fort i Masdevall, Marta; Lopez, Mario A.; Pérez Lantero, Pablo; Urrutia Galicia, Jorge (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 ...
    • IconMonotone crossing number of complete graphs  [Presentation]

      Balko, Martin; Fulek, Radoslav; Kynčl, Jan (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 ...
    • IconPhase transitions in the Ramsey-Turán theory  [Presentation]

      Balogh, József (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 L-free 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 ...
    • IconRecent developments on the crossing number of the complete graph  [Presentation]

      Ramos Alonso, Pedro Antonio (2013)
    • IconFlips in combinatorial pointed pseudo-triangulations with face degree at most four  [Presentation]

      Aichholzer, Oswin; Hackl, Thomas; Orden Martín, David; Pilz, Alexander; Saumell Mendiola, María; Vogtenhuber, Birgit (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 ...
    • IconOn 4-connected geometric graphs  [Presentation]

      García Olaverri, Alfredo; Huemer, Clemens; Tejel Altarriba, Francisco Javier; Valtr, Pavel (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 4-connected non-crossing geometric graph on S.
    • IconSome results on open edge guarding of polygons  [Presentation]

      Bajuelos Domínguez, António Leslie; Canales Cano, Santiago; Hernández Peñalver, Gregorio; Oliveira Martins, Ana Mafalda de; Matos. Inês (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 ...