 Research group
 DCCG  Research group on discrete, combinatorial and computational geometry
 Department
 Department of Applied Mathematics II
 School
 Barcelona School of Informatics (FIB)
 carlos.searaupc.edu
 Contact details
 UPC directory
Scientific and technological production


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. 
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 Segments with Rectilinear Objects
Claverol Aguas, Merce; Seara Ojea, Carlos; Garijo, Delia; Korman Cozzetti, Matias; Silveira, Rodrigo Ignacio
Mexican Conference on Discrete Mathematics and Computational Geometry
Presentation's date: 20131113
Presentation of work at congresses
Read the abstract View Share Reference managersGiven a set of n line segments in the plane, we say that a region R of the plane is a stabber if R contains exactly one end point of each segment of the set. In this paper we provide efficient algorithms for determining wheter or not a stabber exists for several shapes of stabbers. Specially, we consider the case in which the stabber can be described as the intersecction of isothetic halfplanes (thus the stabbers are halfplanes, strips, quadrants, 3sided rectangles, or rectangles). We provided efficient algorithms reporting all combinatorially different stabbers of the shape. The algorithms run in O(n) time (for the halfplane case), O(n logn) time (for strips and quadrants), O(n^2) (for 3sided rectangles), or O(n^3) time (for rectangles).
Given a set of n line segments in the plane, we say that a region R of the plane is a stabber if R contains exactly one end point of each segment of the set. In this paper we provide efficient algorithms for determining wheter or not a stabber exists for several shapes of stabbers. Specially, we consider the case in which the stabber can be described as the intersecction of isothetic halfplanes (thus the stabbers are halfplanes, strips, quadrants, 3sided rectangles, or rectangles). We provided efficient algorithms reporting all combinatorially different stabbers of the shape. The algorithms run in O(n) time (for the halfplane case), O(n logn) time (for strips and quadrants), O(n^2) (for 3sided rectangles), or O(n^3) time (for rectangles). 
New results on stabbing segments with a polygon
Díaz Bañez, José Miguel; Korman Cozzetti, Matias; Pérez Lantero, Pablo; Pilz, Alexander; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
International Conference on Algorithms and Complexity
Presentation's date: 201305
Presentation of work at congresses
Read the abstract View Share Reference managersWe consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon P if at least one of its two endpoints is contained in P. A segment set S is stabbed by P if every segment of S is stabbed by P. We show that if S is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing S can be solved in polynomial time. We also prove that for general segments the problem is NPhard. Further, an adaptation of our polynomialtime algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments.
We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon P if at least one of its two endpoints is contained in P. A segment set S is stabbed by P if every segment of S is stabbed by P. We show that if S is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing S can be solved in polynomial time. We also prove that for general segments the problem is NPhard. Further, an adaptation of our polynomialtime algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments. 
Some structural, metric and convex properties of the boundary of a graph
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos
Ars combinatoria
Date of publication: 20130425
Journal article
Read the abstract Access to the full text Share Reference managersLet u;v be two vertices of a connected graph G . The vertex v is said to be a boundary vertex of u if no neighbor of v is further away from u than v . The boundary of a graph is the set of all its boundary vertices. In this work, we present a number of properties of the boundary of a graph under diÆerent points of view: (1) a realization theorem involving diÆerent types of boundary vertex sets: extreme set, periphery, contour, and the whole boundary; (2) the contour is a monophonic set; and (3) the cardinality of the boundary is an upper bound for both the metric dimension and the determining number of a graph
Let u;v be two vertices of a connected graph G . The vertex v is said to be a boundary vertex of u if no neighbor of v is further away from u than v . The boundary of a graph is the set of all its boundary vertices. In this work, we present a number of properties of the boundary of a graph under diÆerent points of view: (1) a realization theorem involving diÆerent types of boundary vertex sets: extreme set, periphery, contour, and the whole boundary; (2) the contour is a monophonic set; and (3) the cardinality of the boundary is an upper bound for both the metric dimension and the determining number of a graph 
On the number of edges in geometric graphs without empty triangles
Bautista Santiago, Crevel; Heredia, Marco A.; Huemer, Clemens; Ramírez Vigueras, Adriana; Seara Ojea, Carlos; Urrutia Galicia, Jorge
Graphs and combinatorics
Date of publication: 20131101
Journal article
Read the abstract View Share Reference managersIn this paper we study the extremal type problem arising from the question: What is the maximum number ET(S) of edges that a geometric graph G on a planar point set S can have such that it does not contain empty triangles? We prove:(Formula Presented). © 2012 Springer. 
Distinguishing trees in linear time
Lozano Bojados, Antoni; Mora Gine, Mercè; Seara Ojea, Carlos
Electronic journal of combinatorics
Date of publication: 20120521
Journal article
View Share Reference managers 
Minimizing the error of linear separators on linearly inseparable data
Aronov, Boris; Garijo, Delia; Nunez Rodriguez, Yurai; Rappaport, David M.; Seara Ojea, Carlos; Urrutia Galicia, Jorge
Discrete applied mathematics
Date of publication: 201206
Journal article
View Share Reference managers 
Separability of point sets by klevel linear classification trees
Arkin, Esther M.; Garijo, Delia; Márquez, Alberto; Mitchell, Joseph S. B.; Seara Ojea, Carlos
International journal of computational geometry and applications
Date of publication: 201204
Journal article
View Share Reference managers 
Rectilinear convex hull with minimum area
Alegría Galicia, Carlos; Garduño, Tzolkin; Rosas Navarrete, Areli; Seara Ojea, Carlos; Urrutia Galicia, Jorge
Spanish Meeting on Computational Geometry
Presentation's date: 2012
Presentation of work at congresses
View Share Reference managers 
The class cover problem with boxes
Bereg, S.; Cabello, Sergio; Pérez Lantero, Pablo; Díaz Bañez, José Miguel; Seara Ojea, Carlos; Ventura, Inmaculada
Computational geometry: theory and applications
Date of publication: 201208
Journal article
View Share Reference managers 
Stabbers of line segments in the plane
Claverol Aguas, Merce; Garijo, Delia; Grima, Clara; Márquez, Alberto; Seara Ojea, Carlos
Computational geometry: theory and applications
Date of publication: 201107
Journal article
View Share Reference managers 
On computing enclosing isosceles triangles and related problems
Bose, Prosenjit; Mora Gine, Mercè; Seara Ojea, Carlos; Sethia, Saurabh
International journal of computational geometry and applications
Date of publication: 201102
Journal article
Read the abstract Access to the full text Share Reference managersGiven a set of n points in the plane, we show how to compute various enclosing isosceles triangles where different parameters such as area or perimeter are optimized. We then study a 3dimensional version of the problem where we enclose a point set with a cone of fixed aperture $\alpha$. 
Fitting a twojoint orthogonal chain to a point set
Díaz Bañez, José Miguel; López, Mario A.; Mora Gine, Mercè; Seara Ojea, Carlos; Ventura, Inmaculada
Computational geometry: theory and applications
Date of publication: 201104
Journal article
Read the abstract Access to the full text Share Reference managersWe study the problem of fitting a twojoint orthogonal polygonal chain to a set S of n points in the plane, where the objective function is to minimize the maximum orthogonal distance from S to the chain. We show that this problem can be solved in Θ(n) time if the orientation of the chain is fixed, and in Θ(n log n) time when the orientation is not a priori known. We also consider some variations of the problem in threedimensions where a polygonal chain is interpreted as a configuration of orthogonal planes. In this case we obtain O(n) and O(n log n) time algorithms depending on which plane orientations are fixed. 
Distinguishing trees in linear time
Lozano Bojados, Antoni; Mora Gine, Mercè; Seara Ojea, Carlos
Slovenian International Conference on Graph Theory
Presentation's date: 20110624
Presentation of work at congresses
View Share Reference managers 
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 
Facility location problems in the plane based on reverse nearest neighbor queries
Cabello, Sergio; Díaz Bañez, José Miguel; Langerman, Stefan; Seara Ojea, Carlos; Ventura, I
European journal of operational research
Date of publication: 201004
Journal article
View Share Reference managers 
Extremal graph theory for metric dimension and diameter
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Wood, D. R.
Electronic journal of combinatorics
Date of publication: 2010
Journal article
Read the abstract Access to the full text Share Reference managersA set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. Let G ,D be the set of graphs with metric dimension and diameter D. It is wellknown that the minimum order of a graph in G ,D is exactly + D. The first contribution of this paper is to characterise the graphs in G ,D with order + D for all values of and D. Such a characterisation was previously only known for D 6 2 or 6 1. The second contribution is to determine the maximum order of a graph in G ,D for all values of D and . Only a weak upper bound was previously known. 
On the determining number and the metric dimension of graphs
Cáceres, Jose; Garijo, Delia; Puertas, Maria Luz; Seara Ojea, Carlos
Electronic journal of combinatorics
Date of publication: 20100419
Journal article
Read the abstract Access to the full text Share Reference managersThis paper initiates a study on the problem of computing the difference between the metric dimension and the determining number of graphs. We provide new proofs and results on the determining number of trees and Cartesian products of graphs, and establish some lower bounds on the difference between the two parameters. 
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. 
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 
Bichromatic separability with two boxes: A general approach
Cortes, C; Díaz Bañez, José Miguel; PerezLantero, P; Seara Ojea, Carlos; Urrutia, 3J; Ventura, I
Journal of algorithms
Date of publication: 200907
Journal article
Share Reference managers 
Small weak epsilonnets
Aronov, B; Aurenhammer, Franz; Hurtado Diaz, Fernando Alfredo; Langerman, Stefan; Rappaport, D; Seara Ojea, Carlos
Computational geometry: theory and applications
Date of publication: 200907
Journal article
Share Reference managers 
36 twocolored points with no empty monochromatic convex fourgons
Huemer, Clemens; Seara Ojea, Carlos
Geombinatorics
Date of publication: 200907
Journal article
View Share Reference managers 
Stabbers of line segments in the plane
Claverol Aguas, Merce; Garijo, D; Grima, C I; Seara Ojea, Carlos
25th European Workshop on Computational Geometry
Presentation of work at congresses
Share Reference managers 
Stabbers of line segments in the plane
Claverol Aguas, Merce; Garijo, D; Grima, C I; Márquez, A; Seara Ojea, Carlos
Spanish Meeting on Computational Geometry
Presentation of work at congresses
Share Reference managers 
Extremal Graph Theory for Metric Dimension and Diameter
Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Hernando, C; Wood, D R
Date of publication: 200809
Book chapter
Share Reference managers 
Geodeticity of the contour of chordal graphs
Caceres, J; Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M L; Seara Ojea, Carlos
Discrete applied mathematics
Date of publication: 200804
Journal article
Share Reference managers 
Covering point sets with two disjoint disks or squares
Cabello, Sergio; Díaz Bañez, José Miguel; Seara Ojea, Carlos; Sellarès Chiva, Joan Antoni; Urrutia Galicia, Jorge; Ventura, Inmaculada
Computational geometry: theory and applications
Date of publication: 200808
Journal article
View Share Reference managers 
Dimensión métrica de grafos infinitos
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Seara Ojea, Carlos; Cáceres, J; MorenoGonzalez, A; Pelayo Melero, Ignacio Manuel; Puertas, M L
Date of publication: 200703
Book chapter
Share Reference managers 
Extremal Graph Theory for Metric Dimension and Diameter
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Wood, D R
Electronic notes in discrete mathematics
Date of publication: 200708
Journal article
View Share Reference managers 
On the Metric Dimension of Cartesian Products of Graphs
Cáceres, J; Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M L; Seara Ojea, Carlos; Wood, David
SIAM journal on discrete mathematics
Date of publication: 200705
Journal article
Share Reference managers 
On finding widest empty curved corridors
Bereg, S.; Díaz Bañez, José Miguel; Seara Ojea, Carlos; Ventura, Inmaculada
Computational geometry: theory and applications
Date of publication: 200710
Journal article
View Share Reference managers 
Grafos de orden máximo y mínimo con diàmetro y dimensión métrica fijados
Seara Ojea, Carlos; Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Wood, D R
Jornadas de Matemática Discreta y Algorítmica
Presentation's date: 20070713
Presentation of work at congresses
Share Reference managers 
Dimensión métrica de grafos infinitos
Cáceres, J; Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Moreno, A; Pelayo Melero, Ignacio Manuel; Puertas, M L; Seara Ojea, Carlos
Encuentro Andaluz de Matemática Discreta
Presentation's date: 2007
Presentation of work at congresses
Share Reference managers 
Extremal Graph Theory for Metric Dimension and Diameter
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Wood, David
European Conference on Combinatorics, Graph Theory, and Applications
Presentation of work at congresses
Share Reference managers 
On determinig number and metric dimension of graphs
Caceres, J; Garijo, D; Puertas, M L; Seara Ojea, Carlos
Date: 200710
Report
Share Reference managers 
Grafos de orden máximo y mínimo con diámetro y dimensión métrica fijados
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Wood, D R
Date of publication: 200601
Book chapter
Share Reference managers 
On the metric dimension of cartesian products of graphs
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Cáceres, J; Puertas, M L; Wood, D
Date of publication: 200601
Book chapter
Share Reference managers 
On geodetic sets formed by boundary vertices
Cáceres, J; Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M L; Seara Ojea, Carlos
Discrete mathematics
Date of publication: 200602
Journal article
Share Reference managers 
Some structural, metric and convex properties on the boundary of a graph
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos
Electronic notes in discrete mathematics
Date of publication: 200607
Journal article
View Share Reference managers 
Some lower bounds on geometric separability problems
Arkin, E; Hurtado Diaz, Fernando Alfredo; Mitchell, J; Seara Ojea, Carlos; Skiena, S
International journal of computational geometry and applications
Date of publication: 200602
Journal article
Share Reference managers 
On the metric dimension of cartesian product of graphs
Cáceres, J; Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Wood, D
International Workshop on Metric and Convex Graph Theory
Presentation of work at congresses
Share Reference managers 
On the metric dimension of cartesian products of graphs
Cáceres, J; Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Wood, D R
Jornadas de Matemática Discreta y Algorítmica
Presentation's date: 20060713
Presentation of work at congresses
Share Reference managers 
On the metric dimension of some products of graphs
Pelayo Melero, Ignacio Manuel; Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Seara Ojea, Carlos; Wood, D R
SIAM Conference on Discrete Mathematics
Presentation of work at congresses
Share Reference managers 
Some structural, metric and convex properties on the boundary of a graph
Hernando Martin, Maria Del Carmen; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos
Fifth Cracow Conference on Graph Theory "Ustron'06"
Presentation of work at congresses
Share Reference managers 
Metric dimension, diameter and order of a graph
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Wood, D
International Workshop on Metric and Convex Graph Theory
Presentation of work at congresses
Share Reference managers 
El dígrafo excéntrico de un grafo intervalo
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Cáceres, J; Puertas, M L
Date of publication: 200506
Book chapter
Share Reference managers 
Reconstrucción de un grafo a partir de la clausura geodética
Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Cáceres, J; Puertas, M L
Date of publication: 200506
Book chapter
Share Reference managers 
Searching for geodetic boundary vertex sets
Mora Gine, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Cáceres, J; Hernando, C; Puertas, M L
Date of publication: 200501
Book chapter
Share Reference managers
Filter results
UPC network collaboration
Reference managers
Continue