Graphic summary
  • Show / hide key
  • Information


Scientific and technological production
  •  

1 to 50 of 600 results
  • 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.

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

  • 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

  • The alternating path problem revisited

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

  • Witness bar visibility graphs

     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 View View 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

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

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

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

  • Geometric constraint solving in a dynamic geometry framework.

     Hidalgo Garcia, Marta Rosa
    Defense's date: 2013-12-02
    Department of Software, Universitat Politècnica de Catalunya
    Theses

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

    La resolució de restriccions geomètriques és un tema principal en diferents àrees com el modelatge paramètric de sòlids o el disseny assistit per computador. Un problema geomètric en restriccions consisteix en un conjunt d'objectes geomètrics sobre el qual es defineix un conjunt de restriccions. Resoldre el problema geomètric en restriccions significa trobar un emplaçament per als elements geomètrics de forma que el conjunt de restriccions es compleixi.L'objectiu principal de la resolució de restriccions geomètriques és definir estructures rígides. És interessant, però, preguntar-se si té sentit permetre que el valor de les restriccions canviï amb el temps. La resposta és afirmativa. Si assumim un canvi continu en els paràmetres motors, el resultat de la resolució de restriccions geomètriques amb paràmetres motors resulta en la generació de famílies de diferents formes construïdes amb els mateixos elements geomètrics però regit per un conjunt fix derestriccions. Estudiar el problema on diferents paràmetres canvien simultàniament seria una gran fita. Malgrat això, la potencialcomplexitat combinatòria ens obliga a considerar problemes amb un sol paràmetre motor. Basant-nos en el treball d'altres autors, hem desenvolupat un nou algorisme basat en una nova eina anomenada h-graf que resol correctament el problema geomètric en restriccions amb un paràmetre motor. Oferim una demostració completa de la correctesa del mètode que mancava a l'obra original.La geometria dinàmica és una tecnologia desenvolupada per ensenyar geometria als computadors en l'escola, que proporciona als usuaris eines per definir contruccions geomètriques i interactuar amb elles. L'objectiu del sistema és mostrar en la pantalla del computador com la geometria canvia en temps real quan l'usuari interactúa amb el sistema. Aquest tipus d'interacció encoratja l'interés dels estudiants en experimentar i provar les seves idees. L'inconvenient més important de la geometria dinàmica és que és l'usuari el que ha de saber com resoldre el problema geomètric. Basant-nos en el fet que la interacció entre l'usuari i el computador bàsicament permet a l'usuari moure un sol element a la vegada, hem desenvolupat una nova metodologia en geometria dinàmica basada en dues idees: 1) el problema subjacent és simplement un problema geomètric en restriccions amb un paràmetre motor, i, 2) la responsabilitat de resoldre el problema geomètric recau en el resoledor de geometria en restriccions.Dos problemes clàssics i interessants en molts models computacionals són els problemes d'alcançabilitat i traçabilitat. L'alcançabilitat consisteix a decidir si es pot aconseguir transformar un estat inicial del sistema en un determinat estat mitjançant un conjunt de transformacions permeses. Aquest problema és primordial en diferents àrees com robòtica, xarxes de Petri, etc. Quan es trasllada a geometria dinàmica apareixen dos problemes específics: 1) en intersectar elements geomètrics on almenys un d'ells té grau 2 o superior, la solució no és única, i, 2) per als valors donats de les restriccions, podria ser que el problema geomètric no tinguera solució. Per exemple, trobar el punt d'intersecció entre dues rectes paral·leles. Hem desenvolupat un mètode específic en el nostre sistema de geometria dinàmica basada en restriccions que resol tant el problema d'alcançabilitat com el de traçabilitat aplicant eines de teoria de sistemes dinàmics.Finalment considerem grafs de Henneberg, de Laman i tree-decomposables, que són una eina fonamental en la resolució deproblemes en restriccions i les seves aplicacions. Estudiem quines relacions es poden establir entre ells i trobem les condicions sota les quals les construccions de Henneberg conserven la tree-decomposabilitat dels grafs. Per últim desenvolupem un algorisme que genera automàticament grafs de Laman tree-decomposables d'un ordre donat usant construccions de Henneberg.

  • MORFOLOGIA GEOMETRICA COMPUTACIONAL

     Hurtado Diaz, Fernando Alfredo
    Participation in a competitive project

     Share

  • 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)

  • 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

  • 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, $\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, 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, Pedro; 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.

  • 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

  • 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

  • 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, 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

  • 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].

  • 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

  • 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

  • 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

  • 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
    Annual International Conference on Combinatorial Optimization and Applications
    Presentation's date: 2010-12-18
    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

    For a fixed integer k ≥ 0, 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.

  • Access to the full text
    Proximity graphs inside large weighted graphs  Open access

     Ábrego, Bernardo M.; Fabila Monroy, Ruy; Fernández-Merchant, Silvia; Flores Peñazola, David; Hurtado Diaz, Fernando Alfredo; MEIJER, HENK; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    European Workshop on Computational Geometry
    Presentation's date: 2010-03-24
    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

    Given a large weighted graph G = (V;E) and a subset U of V , we de¯ne several graphs with vertex set U in which two vertices are adjacent if they satisfy some prescribed 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 de¯ned graphs and provide algorithms for their computation.

  • Access to the full text
    Some properties of higher order delaunay and gabriel graphs  Open access

     Bose, Prosenjit; Collette, Sébastien; Hurtado Diaz, Fernando Alfredo; Korman, Matias; Langerman, Stefan; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
    Canadian Conference on Computational Geometry
    Presentation's date: 2010-08-09
    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

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

  • Matching points with things

     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 Mendiola, Maria; Seara Ojea, Carlos; Taslakian, Perouz
    Latin American Theoretical Informatics Symposium
    Presentation's date: 2010-04-22
    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

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

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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • On the Chromatic Number of some Flip Graphs

     Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Fabila-Monroy, R; Flores-Penaloza, D; Urrutia, J; Wood, Dr
    Discrete mathematics and theoretical computer science
    Date of publication: 2009-01
    Journal article

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

  • On triconnected and cubic plane graphs on given point sets

     Garcia, A; Hurtado Diaz, Fernando Alfredo; Huemer, Clemens; Tejel, J; Valtr, P
    Computational geometry: theory and applications
    Date of publication: 2009-11
    Journal article

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

  • Compatible geometric matchings

     Aichholzer, O; Bereg, S; Dumitrescu, A; Garcia, A; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Kano, M; Marquez, A; Rappaport, D; Smorodinsky, S; Souvaine, D; Urrutia, J; Wood, Dr
    Computational geometry: theory and applications
    Date of publication: 2009-08
    Journal article

     Share Reference managers Reference managers Open in new window

  • Centerpoint Theorems for Wedges

     Erickson, J; Hurtado Diaz, Fernando Alfredo; Morin, P
    Discrete mathematics and theoretical computer science
    Date of publication: 2009-01
    Journal article

     Share Reference managers Reference managers Open in new window

  • Matching points with squares

     Ábrego, B; Arkin, E; Fernandez Mendez, Sonia; Hurtado Diaz, Fernando Alfredo; Kano, M; Mitchell, J; Urrutia, J
    Discrete and computational geometry
    Date of publication: 2009-01
    Journal article

     Share Reference managers Reference managers Open in new window

  • Flips in planar graphs

     Bose, Prosenjit; Hurtado Diaz, Fernando Alfredo
    Computational geometry: theory and applications
    Date of publication: 2009-01
    Journal article

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