Now showing items 1-20 of 35

    • Icon

      A symbolic-numeric dynamic geometry environment for the computation of equidistant curves  [Presentation]

      Abánades Astudillo, Miguel Ángel; Botana Ferreiro, Francisco (2013)
      A web-based 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 ...
    • Icon

      Abstract 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.
    • Icon

      An 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 ...
    • Icon

      Computing the stretch of an embedded graph  [Presentation]

      Cabello Justo, Sergio; Chimani, Markus; Hliněný, Petr (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 ...
    • Icon

      Continuous 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 ...
    • Icon

      Distance domination, guarding and vertex cover for maximal outerplanar graphs  [Presentation]

      Canales Cano, Santiago; Hernández Peñalver, Gregorio; Oliveira Martins, Ana Mafalda de; Matos. Inês (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 n-vertex maximal ...
    • Icon

      Drawing 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 ...
    • Icon

      Empty convex polytopes in random point sets  [Presentation]

      Balogh, József; González Aguilar, Hernán; Salazar Anaya, Gelasio (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 ...
    • Icon

      Equipartitioning triangles  [Presentation]

      Ramos Alonso, Pedro Antonio; Steiger, William (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 ...
    • Icon

      Flips 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 ...
    • Icon

      Guarding the vertices of thin orthogonal polygons is NP-hard  [Presentation]

      Nunes Gomes Tomás, Ana Paula (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 ...
    • Icon

      Improved 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 ...
    • Icon

      Metaheuristic 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. ...
    • Icon

      Monotone 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 ...
    • Icon

      Note on the number of obtuse angles in point sets  [Presentation]

      Fabila Monroy, Ruy; Huemer, Clemens; Tramuns Figueras, Eulàlia (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 ...
    • Icon

      On 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.
    • Icon

      On 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) ...
    • Icon

      On 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 ...
    • Icon

      On 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 ...
    • Icon

      On 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 ...