 Research group
 DCCG  Research group on discrete, combinatorial and computational geometry
 Department
 Department of Applied Mathematics II
 School
 School of Mathematics and Statistics (FME)
 ferran.hurtadoupc.edu
 Contact details
 UPC directory
 Orcid
 0000000201089671
Scientific and technological production


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: 20140701
Journal article
Read the abstract View Share Reference managersTwo 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. 
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 
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 View Share Reference managersGiven 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 worstcase 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. 
Witness Gabriel graphs
Aronov, Boris; Dulieu, Muriel; Hurtado Diaz, Fernando Alfredo
Computational geometry: theory and applications
Date of publication: 201310
Journal article
Read the abstract View Share Reference managersWe 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. 
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: 201301
Journal article
Read the abstract View Share Reference managersGiven 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 View Share Reference managersGraph 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 crossingfree straightline 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. 
Noncrossing 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: 201301
Journal article
Read the abstract View Share Reference managersGiven an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a noncrossing matching between point¿object pairs. In this paper, we address the algorithmic problem of determining whether a noncrossing 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 NPcomplete 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 NPcomplete 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 minmax noncrossing matching is NPcomplete. 
Some properties of kDelaunay and kGabriel 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: 201302
Journal article
Read the abstract View Share Reference managersWe consider two classes of higher order proximity graphs defined on a set of points in the plane, namely, the kDelaunay graph and the kGabriel 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: 201302
Journal article
Read the abstract View Share Reference managersWe 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. 
MORFOLOGIA GEOMETRICA COMPUTACIONAL
Hurtado Diaz, Fernando Alfredo
Participation in a competitive project
Share 
Distributed universal reconfiguration of 2D latticebased 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 Share Reference managers 
Proximity drawings of highdegree trees
Hurtado Diaz, Fernando Alfredo; Liotta, Giuseppe; Wood, D. R.
International journal of computational geometry and applications
Date of publication: 201306
Journal article
Read the abstract View Share Reference managersA 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 ktransmitters 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: 201302
Journal article
Read the abstract View Share Reference managersFor a fixed integer ka parts per thousand yen0, a ktransmitter 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 ktransmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons. 
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: 201309
Presentation of work at congresses
Read the abstract View Share Reference managersWe 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 redbluepurple 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 NPhard. 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 redbluepurple 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 NPhard. 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. 
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: 20131113
Presentation of work at congresses
Read the abstract Access to the full text Share Reference managersBar 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, witnessbar visibility graphs, and we prove that this class encom passes all the barvisibility 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, witnessbar visibility graphs, and we prove that this class encom passes all the barvisibility 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 
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: 20130628
Presentation of work at congresses
Read the abstract Access to the full text Share Reference managersIt 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 1plane, 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 1plane, 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. 
Stabbing simplices of point sets with kflats
Cano, Javier; Hurtado Diaz, Fernando Alfredo; Urrutia Galicia, Jorge
Spanish Meeting on Computational Geometry
Presentation's date: 20130627
Presentation of work at congresses
Read the abstract Access to the full text Share Reference managersLet S be a set of n points inRdin general position.A set H of kflats is called an mkstabber of S if the relative interior of anymsimplex 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 mkstabbers of point sets in Rd. We study mainly mkstabbers in the plane and in R3
Let S be a set of n points inRdin general position.A set H of kflats is called an mkstabber of S if the relative interior of anymsimplex 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 mkstabbers of point sets in Rd. We study mainly mkstabbers in the plane and in R3 
Generalizing convexity via linear crosssections
Hurtado Diaz, Fernando Alfredo
LatinAmerican Algorithms, Graphs, and Optimization Symposium
Presentation's date: 20130423
Presentation of work at congresses
Share Reference managers 
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 Share Reference managers 
Improving shortest paths in the Delaunay triangulation
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 Access to the full text Share Reference managersWe 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 graphdistance used is Euclidean and for the linkdistance. 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 graphdistance used is Euclidean and for the linkdistance. Several other variations of the problem are also discussed. 
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: 201205
Journal article
View Share Reference managers 
On kconvex 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: 201204
Journal article
View Share Reference managers 
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: 20120320
Presentation of work at congresses
Share Reference managers 
Bichromatic 2center 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: 20120419
Presentation of work at congresses
View Share Reference managers 
Universal point subsets for planar graphs
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: 20121220
Presentation of work at congresses
Read the abstract Access to the full text Share Reference managersA 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 straightline 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 4connected planar graphs and nestedtriangles graphs.
Postprint (author’s final draft) 
On crossing numbers of geometric proximity graphs
Ábrego, Bernardo M.; Fabila Monroy, Ruy; FernándezMerchant, Silvia; FloresPeñaloza, David; Hurtado Diaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria
Computational geometry: theory and applications
Date of publication: 201105
Journal article
View Share Reference managers 
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: 201101
Journal article
Read the abstract View Share Reference managersWe 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: 201107
Journal article
View Share Reference managers 
A generalized Winternitz Theorem
Bose, Prosenjit; Carmi, Paz; Hurtado Diaz, Fernando Alfredo; Morin, Pat
Journal of geometry
Date of publication: 201104
Journal article
View Share Reference managers 
Witness (Delaunay) graphs
Aronov, Boris; Dulieu, Muriel; Hurtado Diaz, Fernando Alfredo
Computational geometry: theory and applications
Date of publication: 201108
Journal article
View Share Reference managers 
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 
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: 20110628
Presentation of work at congresses
View Share Reference managers 
A note on diagonal transformations on maximal planar graphs containing perfect matchings
Hurtado Diaz, Fernando Alfredo; Noy Serrano, Marcos; RiveraCampo, Eduardo
Encuentros de Geometría Computacional
Presentation's date: 20110627
Presentation of work at congresses
View Share Reference managers 
Some problems on proximity graphs
Saumell Mendiola, Maria
Defense's date: 20111129
Department of Applied Mathematics II, Universitat Politècnica de Catalunya
Theses
Share Reference managers 
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: 20110811
Presentation of work at congresses
View Share Reference managers 
Blocking the kholes 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: 20110627
Presentation of work at congresses
View Share Reference managers 
Compatible matchings in geometric graphs
Aichholzer, Oswin; García Olaverri, Alfredo; Hurtado Diaz, Fernando Alfredo; Tejel Altarriba, F. Javier
Encuentros de Geometría Computacional
Presentation's date: 20110627
Presentation of work at congresses
Read the abstract Access to the full text Share Reference managersTwo noncrossing geometric graphs on the same set of points are compatible if their union is also noncrossing. In this paper, we prove that every graph G that has an outerplanar embedding admits a noncrossing perfect matching compatible with G. Moreover, for noncrossing geometric trees and simple polygons, we study bounds on the minimum number of edges that a compatible noncrossing 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: 20110328
Presentation of work at congresses
View Share Reference managers 
Witness rectangle graphs
Aronov, Boris; Dulieu, Muriel; Hurtado Diaz, Fernando Alfredo
Workshop on Algorithms and Data Structures
Presentation's date: 20110815
Presentation of work at congresses
View Share Reference managers 
Large bichromatic point sets admit empty monochromatic 4Gons
Aichholzer, Oswin; Hackl, Thomas; Huemer, Clemens; Hurtado Diaz, Fernando Alfredo; Vogtenhuber, Birgit
SIAM journal on discrete mathematics
Date of publication: 2010
Journal article
View Share Reference managers 
Edgeremoval and noncrossing configurations in geometric graphs
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 Access to the full text Share Reference managersA 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 straightline 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 noncrossing subgraph. The noncrossing 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 3Coloured Disk Packing
Brass, Peter; Hurtado Diaz, Fernando Alfredo; Lafreniere, Benjamin; Lubiw, Anna
International journal of computational geometry and applications
Date of publication: 201007
Journal article
View Share Reference managers 
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: 201002
Journal article
View Share Reference managers 
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: 201002
Journal article
View Share Reference managers 
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 Share Reference managers 
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 
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: 20100422
Presentation of work at congresses
Read the abstract View Share Reference managersGiven an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a noncrossing matching between pointobject pairs. We show that when the objects we match the points to are finite point sets, the problem is NPcomplete 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 NPcomplete 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 minmax noncrossing matching is NPcomplete.
Filter results
UPC network collaboration
Reference managers
Continue