Seara Ojea, Carlos
Total activity: 114

## Scientific and technological production Ordered by:  Date asc. Date desc. Title asc. Title desc. Researcher asc. Researcher desc.

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

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.

• 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

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.

• 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: 2013-11-13
Presentation of work at congresses

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, 3-sided 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 3-sided 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, 3-sided 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 3-sided 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: 2013-05
Presentation of work at congresses

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 NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236-269 (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 NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236-269 (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: 2013-04-25
Journal article

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

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: 2013-11-01
Journal article

In 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: 2012-05-21
Journal article

• 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: 2012-06
Journal article

• Separability of point sets by k-level 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: 2012-04
Journal article

• 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

• 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: 2012-08
Journal article

• 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: 2011-07
Journal article

• 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: 2011-02
Journal article

Given 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 3-dimensional version of the problem where we enclose a point set with a cone of fixed aperture $\alpha$.

• Fitting a two-joint 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: 2011-04
Journal article

We study the problem of fitting a two-joint 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 three-dimensions 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: 2011-06-24
Presentation of work at congresses

• 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

• 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: 2010-04
Journal article

• 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

A 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 well-known 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: 2010-04-19
Journal article

This 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: 2010-04-22
Presentation of work at congresses

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.

• 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

• Bichromatic separability with two boxes: A general approach

Cortes, C; Díaz Bañez, José Miguel; Perez-Lantero, P; Seara Ojea, Carlos; Urrutia, 3J; Ventura, I
Journal of algorithms
Date of publication: 2009-07
Journal article

• Small weak epsilon-nets

Aronov, B; Aurenhammer, Franz; Hurtado Diaz, Fernando Alfredo; Langerman, Stefan; Rappaport, D; Seara Ojea, Carlos
Computational geometry: theory and applications
Date of publication: 2009-07
Journal article

• 36 two-colored points with no empty monochromatic convex fourgons

Huemer, Clemens; Seara Ojea, Carlos
Geombinatorics
Date of publication: 2009-07
Journal article

• 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

• 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

• 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: 2008-09
Book chapter

• 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: 2008-04
Journal article

• 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: 2008-08
Journal article

• Dimensión métrica de grafos infinitos

Hernando Martin, Maria Del Carmen; Mora Gine, Mercè; Seara Ojea, Carlos; Cáceres, J; Moreno-Gonzalez, A; Pelayo Melero, Ignacio Manuel; Puertas, M L
Date of publication: 2007-03
Book chapter

• 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: 2007-08
Journal article

• 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: 2007-05
Journal article

• 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: 2007-10
Journal article

• 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: 2007-07-13
Presentation of work at congresses

• 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

• 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

• On determinig number and metric dimension of graphs

Caceres, J; Garijo, D; Puertas, M L; Seara Ojea, Carlos
Date: 2007-10
Report

• 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: 2006-01
Book chapter

• 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: 2006-01
Book chapter

• 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: 2006-02
Journal article

• 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: 2006-07
Journal article

• 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: 2006-02
Journal article

• 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

• 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: 2006-07-13
Presentation of work at congresses

• 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

• 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

• 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

• 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: 2005-06
Book chapter

• 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: 2005-06
Book chapter

• 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: 2005-01
Book chapter