Graphic summary
  • Show / hide key
  • Information


Scientific and technological production
  •  

1 to 50 of 667 results
  • Compatible spanning trees

     Garcia Olaverri, Alfredo Martin; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Tejel Altarriba, Francisco Javier
    Computational geometry: theory and applications
    Date of publication: 2014-07-01
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Two plane geometric graphs are said to be compatible when their union is a plane geometric graph. Let S be a set of n points in the Euclidean plane in general position and let T be any given plane geometric spanning tree of S. In this work, we study the problem of finding a second plane geometric tree T' spanning S, such that is compatible with T and shares the minimum number of edges with T. We prove that there is always a compatible plane geometric tree T' having at most (n - 3)/4 edges in common with T, and that for some plane geometric trees T, any plane tree T' spanning S, compatible with T, has at least (n - 2)/5 edges in common with T. (C) 2013 Elsevier B.V. All rights reserved.

  • Witness Gabriel graphs

     Aronov, Boris; Dulieu, Muriel; Hurtado Diaz, Fernando Alfredo
    Computational geometry: theory and applications
    Date of publication: 2013-10
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    We consider a generalization of the Gabriel graph, the witness Gabriel graph . Given a set of vertices P and a set of witness points W in the plane, there is an edge ab between two points of P in the witness Gabriel graph GG-(P,W)GG-(P,W) if and only if the closed disk with diameter ab does not contain any witness point (besides possibly a and/or b). We study several properties of the witness Gabriel graph, both as a proximity graph and as a new tool in graph drawing.

  • Coloring and guarding arrangements

     Bose, Prosenjit; Cardinal, Jean; Collette, Sébastien; Hurtado Diaz, Fernando Alfredo; Korman Cozzetti, Matias; Langerman, Stefan; Taslakian, Perouz
    Discrete mathematics and theoretical computer science (Print edition)
    Date of publication: 2013
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Given a simple arrangement of lines in the plane, what is the minimum number c of colors required so that we can color all lines in a way that no cell of the arrangement is monochromatic? In this paper we give worst-case bounds on the number c for both the above question and for some of its variations. Line coloring problems can be redefined as geometric hypergraph coloring problems as follows: if we define Hline¿cell as the hypergraph whose vertices are lines and edges are cells of the arrangement, then c is equal to the chromatic number of this hypergraph. Specifically, we prove that this chromatic number is between (log n= log log n) and O( p n). Furthermore, we give bounds on the minimum size of a subset S of the intersection points between pairs of lines in A such that every cell contains at least a vertex of S. This may be seen as the problem of guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph Hvertex¿cell, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the Hcell¿zone hypergraph.

  • Proximity graphs inside large weighted graphs

     Ábrego, Bernardo M.; Fabila Monroy, Ruy; Fernández Merchant, Silvia; Flores Peñaloza, David; Hurtado Diaz, Fernando Alfredo; Meijer, Henk G. E.; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    Networks
    Date of publication: 2013-01
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Given a weighted graph G = (V,E) and a subset U of V, we define several graphs with vertex set U in which two vertices are adjacent if they satisfy a specific proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the defined graphs and provide algorithms for their computation.

  • Non-crossing matchings of points with geometric objects

     Aloupis, Greg; Cardinal, Jean; Collette, Sébastien; Demaine, Erik D.; Demaine, Martin L.; Dulieu, Muriel; Fabila Monroy, Ruy; Hart, Vi; Hurtado Diaz, Fernando Alfredo; Langerman, Stefan; Saumell, Maria; Seara Ojea, Carlos; Taslakian, Perouz
    Computational geometry: theory and applications
    Date of publication: 2013-01
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point¿object pairs. In this paper, we address the algorithmic problem of determining whether a non-crossing matching exists between a given point¿object pair. We show that when the objects we match the points to are finite point sets, the problem is NP-complete in general, and polynomial when the objects are on a line or when their size is at most 2. When the objects are line segments, we show that the problem is NP-complete in general, and polynomial when the segments form a convex polygon or are all on a line. Finally, for objects that are straight lines, we show that the problem of finding a min-max non-crossing matching is NP-complete.

  • Some properties of k-Delaunay and k-Gabriel graphs

     Bose, Prosenjit; Collette, Sébastien; Hurtado Diaz, Fernando Alfredo; Korman Cozzetti, Matias; Langerman, Stefan; Sacristán Adinolfi, Vera; Saumell, Maria
    Computational geometry: theory and applications
    Date of publication: 2013-02
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    We consider two classes of higher order proximity graphs defined on a set of points in the plane, namely, the k-Delaunay graph and the k-Gabriel graph. We give bounds on the following combinatorial and geometric properties of these graphs: spanning ratio, diameter, connectivity, chromatic number, and minimum number of layers necessary to partition the edges of the graphs so that no two edges of the same layer cross.

  • Measuring regularity of convex polygons

     Chalmeta Ugas, Ramon; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Masalles Saumell, Ramon Maria
    Computer Aided Design
    Date of publication: 2013-02
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    We propose several measures to evaluate to which extent the shape of a given convex polygon is close to be regular, focusing on a range of characteristics of regularity: optimal ratio area¿perimeter, equality of angles and edge lengths, regular fitting, angular and areal symmetry. We prove that our measures satisfy a number of reasonable requirements that guarantee them to be well defined, and provide efficient algorithms for their computation. All these algorithms have been implemented, and we provide experimental results on all the proposed measures.

  • Proximity drawings of high-degree trees

     Hurtado Diaz, Fernando Alfredo; Liotta, Giuseppe; Wood, D. R.
    International journal of computational geometry and applications
    Date of publication: 2013-06
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    A drawing of a given (abstract) tree that is a minimum spanning tree of the vertex set is considered aesthetically pleasing. However, such a drawing can only exist if the tree has maximum degree at most 6. What can be said for trees of higher degree? We approach this question by supposing that a partition or covering of the tree by subtrees of bounded degree is given. Then we show that if the partition or covering satisfies some natural properties, then there is a drawing of the entire tree such that each of the given subtrees is drawn as a minimum spanning tree of its vertex set.

  • Coverage with k-transmitters in the presence of obstacles

     Ballinger, Brad; Benbernou, Nadia; Bose, Prosenjit; Damian, Mirela; Demaine, Erik D.; Dujmovic, Vida; Flatland, Robin; Hurtado Diaz, Fernando Alfredo; Iacono, John; Lubiw, Anna; Morin, Pat; Sacristán Adinolfi, Vera; Souvaine, Diane; Uehara, Ryuhei
    Journal of combinatorial optimization
    Date of publication: 2013-02
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    For a fixed integer ka parts per thousand yen0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k "walls", represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons.

  • MORFOLOGIA GEOMETRICA COMPUTACIONAL

     Hurtado Diaz, Fernando Alfredo
    Participation in a competitive project

     Share

  • Computational geometry: theory and applications

     Hurtado Diaz, Fernando Alfredo
    Collaboration in journals

     Share

  • Discrete and computational geometry

     Hurtado Diaz, Fernando Alfredo
    Collaboration in journals

     Share

  • Plane geometric graph augmentation: a generic perspective

     Hurtado Diaz, Fernando Alfredo; Tóth, Csaba D.
    Date of publication: 2013
    Book chapter

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    Graph augmentation problems are motivated by network design and have been studied extensively in optimization. We consider augmentation problems over plane geometric graphs, that is, graphs given with a crossing-free straight-line embedding in the plane. The geometric constraints on the possible new edges render some of the simplest augmentation problems intractable, and in many cases only extremal results are known. We survey recent results, highlight common trends, and gather numerous conjectures and open problems.

  • Colored spanning graphs for set visualization

     Hurtado Diaz, Fernando Alfredo; Korman Cozzetti, Matias; Van Kreveld, Matias; Löffler, Maarten; Sacristán Adinolfi, Vera; Silveira, Rodrigo Ignacio; Speckmann, Bettina
    Symposium on Graph Drawing
    Presentation's date: 2013-09
    Presentation of work at congresses

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem is NP-hard. Hence we give an (1/2¿+1)-approximation, where ¿ is the Steiner ratio. We also present efficient exact solutions if the points are located on a line or a circle. Finally we consider extensions to more than two sets.

    We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem is NP-hard. Hence we give an (1/2¿+1)-approximation, where ¿ is the Steiner ratio. We also present efficient exact solutions if the points are located on a line or a circle. Finally we consider extensions to more than two sets.

  • Access to the full text
    Witness bar visibility graphs  Open access

     Cortés, Carmen; Hurtado Diaz, Fernando Alfredo; Márquez, Alberto; Valenzuela, Jesús
    Mexican Conference on Discrete Mathematics and Computational Geometry
    Presentation's date: 2013-11-13
    Presentation of work at congresses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    Bar visibility graphs were introduced in the seventies as a model for some VLSI layout problems. They have been also studied since then by the graph drawing community, and recently several generalizations and restricted versions have been proposed. We introduce a generalization, witness-bar visibility graphs, and we prove that this class encom- passes all the bar-visibility variations considered so far. In addition, we show that many classes of graphs are contained in this family, including in particular all planar graphs, interval graphs, circular arc graphs and permutation graphs

    Bar visibility graphs were introduced in the seventies as a model for some VLSI layout problems. They have been also studied since then by the graph drawing community, and recently several generalizations and restricted versions have been proposed. We introduce a generalization, witness-bar visibility graphs, and we prove that this class encom- passes all the bar-visibility variations considered so far. In addition, we show that many classes of graphs are contained in this family, including in particular all planar graphs, interval graphs, circular arc graphs and permutation graphs

  • Generalizing convexity via linear cross-sections

     Hurtado Diaz, Fernando Alfredo
    Latin-American Algorithms, Graphs, and Optimization Symposium
    Presentation's date: 2013-04-23
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • Access to the full text
    The alternating path problem revisited  Open access

     Claverol Aguas, Merce; Garijo, Delia; Hurtado Diaz, Fernando Alfredo; Lara Cuevas, Maria Dolores; Seara Ojea, Carlos
    Spanish Meeting on Computational Geometry
    Presentation's date: 2013-06-28
    Presentation of work at congresses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    It is well known that, given n red points and n blue points on a circle, it is not always possible to and a plane geometric Hamiltonian alternating path. In this work we prove that if we relax the constraint on the path from being plane to being 1-plane, then the problem always has a solution, and even a Hamiltonian alternating cycle can be obtained on all instances. We also extend this kind of result to other configurations and provide remarks on similar problems.

    It is well known that, given "n" red points and "n" blue points on acircle, it is not always possible to find a plane geometric. Hamiltonian alternating path. In this work we prove that if we relax the constraint on the path from being plane to being 1-plane, then the problem always has a solution, and even a Hamiltonian alternating cycle can be obtained on all instances. we also extend this kind of result to other configurations and provide remarks on similar problems.

  • Access to the full text
    Stabbing simplices of point sets with k-flats  Open access

     Cano, Javier; Hurtado Diaz, Fernando Alfredo; Urrutia Galicia, Jorge
    Spanish Meeting on Computational Geometry
    Presentation's date: 2013-06-27
    Presentation of work at congresses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    Let S be a set of n points inRdin general position.A set H of k-flats is called an mk-stabber of S if the relative interior of anym-simplex with vertices in S is intersected by at least one element of H. In thispaper we give lower and upper bounds on the size of mínimum mk-stabbers of point sets in Rd. We study mainly mk-stabbers in the plane and in R3

    Let S be a set of n points inRdin general position.A set H of k-flats is called an mk-stabber of S if the relative interior of anym-simplex with vertices in S is intersected by at least one element of H. In thispaper we give lower and upper bounds on the size of mínimum mk-stabbers of point sets in Rd. We study mainly mk-stabbers in the plane and in R3

  • Distributed universal reconfiguration of 2D lattice-based modular robots

     Hurtado Diaz, Fernando Alfredo; Molina Sarazá, Enrique; Ramaswami, Suneeta; Sacristán Adinolfi, Vera
    European Workshop on Computational Geometry
    Presentation's date: 2013
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Proximity graphs: E, $\delta$, $\Delta$, $\Chi$ and $\omega$

     Bose, Prosenjit; Dumovic, V.; Hurtado Diaz, Fernando Alfredo; Iacono, John; Langerman, Stefan; Meijer, H; Sacristán Adinolfi, Vera; Saumell, Maria; Wood, David R.
    International journal of computational geometry and applications
    Date of publication: 2012
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Token Graphs

     Fabila Monroy, Ruy; Flores Peñaloza, David; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Urrutia Galicia, Jorge; Wood, David R.
    Graphs and combinatorics
    Date of publication: 2012-05
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • On k-convex polygons

     Aichholzer, Oswin; Aurenhammer, Franz; Demaine, Erik D.; Hurtado Diaz, Fernando Alfredo; Ramos Alonso, Pedro Antonio; Urrutia Galicia, Jorge
    Computational geometry: theory and applications
    Date of publication: 2012-04
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Access to the full text
    Improving shortest paths in the Delaunay triangulation  Open access

     Claverol Aguas, Merce; Hernández Peñalver, Gregorio; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell, Maria; Silveira, Rodrigo Ignacio; Abellanas, Manuel
    International journal of computational geometry and applications
    Date of publication: 2012
    Journal article

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set S, we look for a new point p ¿ S that can be added, such that the shortest path from s to t, in the Delaunay triangulation of S¿{p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such a point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.

    We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set P, we look for a new point p that can be added, such that the shortest path from s to t, in the Delaunay triangulation of P ∪ {p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.

  • Bichromatic 2-center of pairs of points

     Arkin, Esther M.; Díaz Bañez, José Miguel; Hurtado Diaz, Fernando Alfredo; Kumar, Piyush; Mitchell, Joseph S. B.; Palop, Belén; Pérez Lantero, Pablo; Saumell, Maria; Silveira, Rodrigo Ignacio
    Latin American Symposium on Theoretical Informatics
    Presentation's date: 2012-04-19
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Proximity graphs: E, d, D, X.

     Bose, Prosenjit; Dujmovic, Vida; Hurtado Diaz, Fernando Alfredo; Iacono, J.; Langerman, Stefan; Meijer, H.; Sacristán Adinolfi, Vera; Saumell, Maria; Wood, D. R.
    European Workshop on Computational Geometry
    Presentation's date: 2012-03-20
    Presentation of work at congresses

     Share Reference managers Reference managers Open in new window

  • Access to the full text
    Universal point subsets for planar graphs  Open access

     Angelini, Patrizio; Binucci, Carla; Evans, William; Hurtado Diaz, Fernando Alfredo; Liotta, Giuseppe; Mchedlidze, Tamara; Meijer, Henk; Okamoto, Yoshio
    International Symposium on Algorithms and Computation
    Presentation's date: 2012-12-20
    Presentation of work at congresses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    A set S of k points in the plane is a universal point subset for a class G of planar graphs if every graph belonging to G admits a planar straight-line drawing such that k of its vertices are represented by the points of S . In this paper we study the following main problem: For a given class of graphs, what is the maximum k such that there exists a universal point subset of size k ? We provide a ⌈ √ n ⌉ lower bound on k for the class of planar graphs with n ver- tices. In addition, we consider the value F ( n; G ) such that every set of F ( n; G ) points in general position is a universal subset for all graphs with n vertices be- longing to the family G , and we establish upper and lower bounds for F ( n; G ) for different families of planar graphs, including 4-connected planar graphs and nested-triangles graphs.

    Postprint (author’s final draft)

  • Some problems on proximity graphs

     Saumell Mendiola, Maria
    Defense's date: 2011-11-29
    Department of Applied Mathematics II, Universitat Politècnica de Catalunya
    Theses

     Share Reference managers Reference managers Open in new window

  • Coverage restricted to an angle

     Bajuelos, Antonio L.; Hurtado Diaz, Fernando Alfredo; Pereira de Matos, Ines; Abellanas, Manuel
    Operations research letters
    Date of publication: 2011-07
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Witness (Delaunay) graphs

     Aronov, Boris; Dulieu, Muriel; Hurtado Diaz, Fernando Alfredo
    Computational geometry: theory and applications
    Date of publication: 2011-08
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • A generalized Winternitz Theorem

     Bose, Prosenjit; Carmi, Paz; Hurtado Diaz, Fernando Alfredo; Morin, Pat
    Journal of geometry
    Date of publication: 2011-04
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • On crossing numbers of geometric proximity graphs

     Ábrego, Bernardo M.; Fabila Monroy, Ruy; Fernández-Merchant, Silvia; Flores-Peñaloza, David; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    Computational geometry: theory and applications
    Date of publication: 2011-05
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Every large point set contains many collinear points or an empty pentagon

     Abel, Zachary; Ballinger, Brad; Bose, Prosenjit; Collette, Sébastien; Dujmovic, Vida; Hurtado Diaz, Fernando Alfredo; Kominers, Scott Duke; Langerman, Stefan; Por, Attila; Wood, David R.
    Graphs and combinatorics
    Date of publication: 2011-01
    Journal article

    Read the abstract Read the abstract View View Open in new window  Share Reference managers Reference managers Open in new window

    We prove the following generalised empty pentagon theorem for every integer ℓ ≥ 2, every sufficiently large set of points in the plane contains ℓ collinear points or an empty pentagon. As an application, we settle the next open case of the “big line or big clique” conjecture of Kára, Pór, and Wood [Discrete Comput. Geom. 34(3):497–506, 2005].

  • MATHEMATICAL FOUNDATIONS OF HIGH QUALITY TERRAIN MODELS

     Silveira, Rodrigo Ignacio; Hurtado Diaz, Fernando Alfredo
    Participation in a competitive project

     Share

  • Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)

     Claverol Aguas, Merce; Dall, Aaron Matthew; Silveira, Rodrigo Ignacio; Huemer, Clemens; Mora Gine, Mercè; Sacristán Adinolfi, Vera; Hernando Martin, Maria Del Carmen; Seara Ojea, Carlos; Montes Lozano, Antonio; Hurtado Diaz, Fernando Alfredo
    Participation in a competitive project

     Share

  • International journal of computational geometry and applications

     Hurtado Diaz, Fernando Alfredo
    Collaboration in journals

     Share

  • Convexifying polygons without losing visibilities

     Aichholzer, Oswin; Aloupis, Greg; Demaine, Erik D.; Demaine, Martin L.; Dujmovic, Vida; Hurtado Diaz, Fernando Alfredo; Lubiw, Anna; Rote, Günter; Schulz, André; Souvaine, Diane; Winslow, Andrew
    Canadian Conference on Computational Geometry
    Presentation's date: 2011-08-11
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Blocking the k-holes of point sets on the plane

     Cano, Javier; García, Alfredo; Hurtado Diaz, Fernando Alfredo; Sakai, Toshinori; Tejel Altarriba, Francisco Javier; Urrutia Galicia, Jorge
    Encuentros de Geometría Computacional
    Presentation's date: 2011-06-27
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Access to the full text
    Compatible matchings in geometric graphs  Open access

     Aichholzer, Oswin; García Olaverri, Alfredo; Hurtado Diaz, Fernando Alfredo; Tejel Altarriba, F. Javier
    Encuentros de Geometría Computacional
    Presentation's date: 2011-06-27
    Presentation of work at congresses

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    Two non-crossing geometric graphs on the same set of points are compatible if their union is also non-crossing. In this paper, we prove that every graph G that has an outerplanar embedding admits a non-crossing perfect matching compatible with G. Moreover, for non-crossing geometric trees and simple polygons, we study bounds on the minimum number of edges that a compatible non-crossing perfect matching must share with the tree or the polygon. We also give bounds on the maximal size of a compatible matching (not necessarily perfect) that is disjoint from the tree or the polygon.

  • Improving shortest paths in the Delaunay triangulation

     Claverol Aguas, Merce; Hernández Peñalver, Gregorio; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria; Silveira, Rodrigo Ignacio; Abellanas, Manuel
    European Workshop on Computational Geometry
    Presentation's date: 2011-03-28
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Improving shortest paths in the Delaunay triangulation

     Claverol Aguas, Merce; Hernández, Gregorio; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria; Silveira, Rodrigo Ignacio; Abellanas, Manuel
    Spanish Meeting on Computational Geometry
    Presentation's date: 2011-06-28
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Witness rectangle graphs

     Aronov, Boris; Dulieu, Muriel; Hurtado Diaz, Fernando Alfredo
    Workshop on Algorithms and Data Structures
    Presentation's date: 2011-08-15
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • A note on diagonal transformations on maximal planar graphs containing perfect matchings

     Hurtado Diaz, Fernando Alfredo; Noy Serrano, Marcos; Rivera-Campo, Eduardo
    Encuentros de Geometría Computacional
    Presentation's date: 2011-06-27
    Presentation of work at congresses

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Augmenting the Connectivity of Outerplanar Graphs

     García Olaverri, Alfredo; Hurtado Diaz, Fernando Alfredo; Noy Serrano, Marcos; Tejel Altarriba, F. Javier
    Algorithmica
    Date of publication: 2010-02
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Highway hull revisited

     Aloupis, Greg; Cardinal, Jean; Collette, Sébastien; Hurtado Diaz, Fernando Alfredo; Langerman, Stefan; O'Rourke, Joseph; Palop Del Rio, Belén
    Computational geometry: theory and applications
    Date of publication: 2010-02
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Resultados algorítmicos y combinatorios sobre gráficas geométricas

     Flores Peñaloza, David
    Defense's date: 2010-03-08
    Universidad Nacional Autónoma de México
    Theses

     Share Reference managers Reference managers Open in new window

  • Access to the full text
    Edge-removal and non-crossing configurations in geometric graphs  Open access

     Aichholzer, Oswin; Cabello, Sergio; Fabila Monroy, Ruy; Flores Peñazola, David; Hackl, Thomas; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Wood, D. R.
    Discrete mathematics and theoretical computer science
    Date of publication: 2010
    Journal article

    Read the abstract Read the abstract Access to the full text Access to the full text Open in new window  Share Reference managers Reference managers Open in new window

    A geometric graph is a graph G = (V;E) drawn in the plane, such that V is a point set in general position and E is a set of straight-line segments whose endpoints belong to V . We study the following extremal problem for geometric graphs: How many arbitrary edges can be removed from a complete geometric graph with n vertices such that the remaining graph still contains a certain non-crossing subgraph. The non-crossing subgraphs that we consider are perfect matchings, subtrees of a given size, and triangulations. In each case, we obtain tight bounds on the maximum number of removable edges.

  • A Lower Bound on the Area of a 3-Coloured Disk Packing

     Brass, Peter; Hurtado Diaz, Fernando Alfredo; Lafreniere, Benjamin; Lubiw, Anna
    International journal of computational geometry and applications
    Date of publication: 2010-07
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Transforming triangulations on nonplanar surfaces

     Cortes, C.; Grima, C. I.; Hurtado Diaz, Fernando Alfredo; Márquez, Alberto; Santos, Francisco; Valenzuela, Juan Carlos
    SIAM journal on discrete mathematics
    Date of publication: 2010
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • Large bichromatic point sets admit empty monochromatic 4-Gons

     Aichholzer, Oswin; Hackl, Thomas; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Vogtenhuber, Birgit
    SIAM journal on discrete mathematics
    Date of publication: 2010
    Journal article

    View View Open in new window  Share Reference managers Reference managers Open in new window

  • PROBLEMAS DE COMBINATORIA Y DE COMPUTACION

     Claverol Aguas, Merce; Hernando Martin, Maria Del Carmen; Montes Lozano, Antonio; Mora Gine, Mercè; Sacristán Adinolfi, Vera; Seara Ojea, Carlos; Trias Pairo, Juan; Huemer, Clemens; Pfeifle, Julian Thoralf; Saumell Mendiola, Maria; Garcia Olaverri, Alfredo Martin; Tejel Altarriba, Francisco Javier; Dall, Aaron Matthew; Hurtado Diaz, Fernando Alfredo
    Participation in a competitive project

     Share