Source author record

Jorge Urrutia

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry math.CO Discrete Mathematics Robotics

Catalog footprint

Research overview

15works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Algorithms for the Euclidean Bipartite Edge Cover Problem

Given a graph $G=(V,E)$ with costs on its edges, the minimum-cost edge cover problem consists of finding a subset of $E$ covering all vertices in $V$ at minimum cost. If $G$ is bipartite, this problem can be solved in time $O(|V|^3)$ via a well-known reduction to a maximum-cost matching problem on $G$ . If in addition $V$ is a set of points on the Euclidean line, Collanino et al. showed that the problem can be solved in time $O(|V| \log |V|)$ and asked whether it can be solved in time $o(|V|^3)$ if $V$ is a set of points on the Euclidean plane. We answer this in the affirmative, giving an $O(|V|^{2.5} \log |V|)$ algorithm based on the Hungarian method using weighted Voronoi diagrams. We also propose some 2-approximation algorithms and give experimental results of our implementations.

preprint2022arXiv

Convex polygons and separation of convex sets

We prove that for any collection F of $n \ge 2$ pairwise disjoint compact convex sets in the plane there is a pair of sets A and B in F such that any line that separates A from B separates either A or B from a subcollection of F with at least n/18 sets.

preprint2022arXiv

Rectilinear Convex Hull of Points in 3D

Let $P$ be a set of $n$ points in $\mathbb{R}^3$ in general position, and let $RCH(P)$ be the rectilinear convex hull of $P$ . In this paper we obtain an optimal $O(n\log n)$ -time and $O(n)$ -space algorithm to compute $RCH(P)$ . We also obtain an efficient $O(n\log^2 n)$ -time and $O(n\log n)$ -space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of $P$ as we rotate $\mathbb R^3$ around the $z$ -axis. Finally we study some properties of the rectilinear convex hulls of point sets in $\mathbb{R}^3$ .

preprint2022arXiv

Separating bichromatic point sets in the plane by restricted orientation convex hulls

We explore the separability of point sets in the plane by a restricted-orientation convex hull, which is an orientation-dependent, possibly disconnected, and non-convex enclosing shape that generalizes the convex hull. Let $R$ and $B$ be two disjoint sets of red and blue points in the plane, and $\mathcal{O}$ be a set of $k \geq 2$ lines passing through the origin. We study the problem of computing the set of orientations of the lines of $\mathcal{O}$ for which the $\mathcal{O}$ -convex hull of $R$ contains no points of $B$ . For $k=2$ orthogonal lines we have the rectilinear convex hull. In optimal $O(n \log n)$ time and $O(n)$ space, $n = \vert R \vert + \vert B \vert$ , we compute the set of rotation angles such that, after simultaneously rotating the lines of $\mathcal{O}$ around the origin in the same direction, the rectilinear convex hull of $R$ contains no points of $B$ . We generalize this result to the case where $\mathcal{O}$ is formed by $k \geq 2$ lines with arbitrary orientations. In the counter-clockwise circular order of the lines of $\mathcal{O}$ , let $α_i$ be the angle required to clockwise rotate the $i$ th line so it coincides with its successor. We solve the problem in this case in $O(1/Θ\cdot N \log N)$ time and $O(1/Θ\cdot N)$ space, where $Θ= \min \{ α_1,\ldots,α_k \}$ and $N=\max\{k,\vert R \vert + \vert B \vert \}$ . We finally consider the case in which $\mathcal{O}$ is formed by $k=2$ lines, one of the lines is fixed, and the second line rotates by an angle that goes from $0$ to $π$ . We show that this last case can also be solved in optimal $O(n\log n)$ time and $O(n)$ space, where $n = \vert R \vert + \vert B \vert$ .

preprint2020arXiv

A Note on Empty Balanced Tetrahedra in Two colored Point sets in $\mathbb{R}^3$

Let $S$ be a set of $n$ red and $n$ blue points in general position in $\mathbb{R}^3$ . Let $τ$ be a tetrahedra with vertices on $S$ . We say that $τ$ is \emph{empty} if it does not contain any point of $S$ in its interior. We say that $τ$ is \emph{balanced} if it contains two blue vertices and two red vertices. In this paper we show that $S$ spans $Ω(n^{5/2})$ empty balanced tetrahedra.

preprint2020arXiv

Minimizing The Maximum Distance Traveled To Form Patterns With Systems of Mobile Robots

In the pattern formation problem, robots in a system must self-coordinate to form a given pattern, regardless of translation, rotation, uniform-scaling, and/or reflection. In other words, a valid final configuration of the system is a formation that is \textit{similar} to the desired pattern. While there has been no shortage of research in the pattern formation problem under a variety of assumptions, models, and contexts, we consider the additional constraint that the maximum distance traveled among all robots in the system is minimum. Existing work in pattern formation and closely related problems are typically application-specific or not concerned with optimality (but rather feasibility). We show the necessary conditions any optimal solution must satisfy and present a solution for systems of three robots. Our work also led to an interesting result that has applications beyond pattern formation. Namely, a metric for comparing two triangles where a distance of $0$ indicates the triangles are similar, and $1$ indicates they are \emph{fully dissimilar}.

preprint2018arXiv

Capturing points with a rotating polygon (and a 3D extension)

We study the problem of rotating a simple polygon to contain the maximum number of elements from a given point set in the plane. We consider variations of this problem where the rotation center is a given point or lies on a line segment, a line, or a polygonal chain. We also solve an extension to 3D where we rotate a polyhedron around a given point to contain the maximum number of elements from a set of points in the space.

preprint2015arXiv

Geometric Spanning Cycles in Bichromatic Point Sets

Given a set of points in the plane each colored either red or blue, we find non-self-intersecting geometric spanning cycles of the red points and of the blue points such that each edge of the red spanning cycle is crossed at most three times by the blue spanning cycle and vice-versa.

preprint2015arXiv

Modem Illumination of Monotone Polygons

We study a generalization of the classical problem of the illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number $k$ of walls. We call these objects $k$ -modems and study the minimum number of $k$ -modems sufficient and sometimes necessary to illuminate monotone and monotone orthogonal polygons. We show that every monotone polygon with $n$ vertices can be illuminated with $\big\lceil \frac{n-2}{2k+3} \big\rceil$ $k$ -modems. In addition, we exhibit examples of monotone polygons requiring at least $\lceil \frac {n-2} {2k+3}\rceil$ $k$ -modems to be illuminated. For monotone orthogonal polygons with $n$ vertices we show that for $k=1$ and for even $k$ , every such polygon can be illuminated with $\big\lceil \frac{n-2}{2k+4} \big\rceil$ $k$ -modems, while for odd $k\geq3$ , $\big\lceil \frac{n-2}{2k+6} \big\rceil$ $k$ -modems are always sufficient. Further, by presenting according examples of monotone orthogonal polygons, we show that both bounds are tight.

preprint2014arXiv

On $k$ -Gons and $k$ -Holes in Point Sets

We consider a variation of the classical Erdős-Szekeres problems on the existence and number of convex $k$ -gons and $k$ -holes (empty $k$ -gons) in a set of $n$ points in the plane. Allowing the $k$ -gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any $k$ and sufficiently large $n$ , we give a quadratic lower bound for the number of $k$ -holes, and show that this number is maximized by sets in convex position.

preprint2012arXiv

Empty Monochromatic Simplices

Let $S$ be a $k$ -colored (finite) set of $n$ points in $\mathbb{R}^d$ , $d\geq 3$ , in general position, that is, no { $(d + 1)$ } points of $S$ lie in a common $(d - 1)$ }-dimensional hyperplane. We count the number of empty monochromatic $d$ -simplices determined by $S$ , that is, simplices which have only points from one color class of $S$ as vertices and no points of $S$ in their interior. For $3 \leq k \leq d$ we provide a lower bound of $Ω(n^{d-k+1+2^{-d}})$ and strengthen this to $Ω(n^{d-2/3})$ for $k=2$ . On the way we provide various results on triangulations of point sets in $\mathbb{R}^d$ . In particular, for any constant dimension $d\geq3$ , we prove that every set of $n$ points ( $n$ sufficiently large), in general position in $\mathbb{R}^d$ , admits a triangulation with at least $dn+Ω(\log n)$ simplices.

preprint2012arXiv

Hamiltonian Tetrahedralizations with Steiner Points

Let $S$ be a set of $n$ points in 3-dimensional space. A tetrahedralization $\mathcal{T}$ of $S$ is a set of interior disjoint tetrahedra with vertices on $S$ , not containing points of $S$ in their interior, and such that their union is the convex hull of $S$ . Given $\mathcal{T}$ , $D_\mathcal{T}$ is defined as the graph having as vertex set the tetrahedra of $\mathcal{T}$ , two of which are adjacent if they share a face. We say that $\mathcal{T}$ is Hamiltonian if $D_\mathcal{T}$ has a Hamiltonian path. Let $m$ be the number of convex hull vertices of $S$ . We prove that by adding at most $\lfloor \frac{m-2}{2} \rfloor$ Steiner points to interior of the convex hull of $S$ , we can obtain a point set that admits a Hamiltonian tetrahedralization. An $O(m^{3/2}) + O(n \log n)$ time algorithm to obtain these points is given. We also show that all point sets with at most 20 convex hull points admit a Hamiltonian tetrahedralization without the addition of any Steiner points. Finally we exhibit a set of 84 points that does not admit a Hamiltonian tetrahedralization in which all tetrahedra share a vertex.

preprint2012arXiv

On the Connectedness and Diameter of a Geometric Johnson Graph

Let $P$ be a set of $n$ points in general position in the plane. A subset $I$ of $P$ is called an \emph{island} if there exists a convex set $C$ such that $I = P \cap C$ . In this paper we define the \emph{generalized island Johnson graph} of $P$ as the graph whose vertex consists of all islands of $P$ of cardinality $k$ , two of which are adjacent if their intersection consists of exactly $l$ elements. We show that for large enough values of $n$ , this graph is connected, and give upper and lower bounds on its diameter.

preprint2010arXiv

On k-Convex Polygons

We introduce a notion of $k$ -convexity and explore polygons in the plane that have this property. Polygons which are \mbox{ $k$ -convex} can be triangulated with fast yet simple algorithms. However, recognizing them in general is a 3SUM-hard problem. We give a characterization of \mbox{ $2$ -convex} polygons, a particularly interesting class, and show how to recognize them in \mbox{ $O(n \log n)$ } time. A description of their shape is given as well, which leads to Erdős-Szekeres type results regarding subconfigurations of their vertex sets. Finally, we introduce the concept of generalized geometric permutations, and show that their number can be exponential in the number of \mbox{ $2$ -convex} objects considered.

preprint2009arXiv

Token Graphs

For a graph $G$ and integer $k\geq1$ , we define the token graph $F_k(G)$ to be the graph with vertex set all $k$ -subsets of $V(G)$ , where two vertices are adjacent in $F_k(G)$ whenever their symmetric difference is a pair of adjacent vertices in $G$ . Thus vertices of $F_k(G)$ correspond to configurations of $k$ indistinguishable tokens placed at distinct vertices of $G$ , where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jorge Urrutia

Research overview

Is this your work?

15 publications

Algorithms for the Euclidean Bipartite Edge Cover Problem

Convex polygons and separation of convex sets

Rectilinear Convex Hull of Points in 3D

Separating bichromatic point sets in the plane by restricted orientation convex hulls

A Note on Empty Balanced Tetrahedra in Two colored Point sets in $\mathbb{R}^3$

Minimizing The Maximum Distance Traveled To Form Patterns With Systems of Mobile Robots

Capturing points with a rotating polygon (and a 3D extension)

Geometric Spanning Cycles in Bichromatic Point Sets

Modem Illumination of Monotone Polygons

On $k$ -Gons and $k$ -Holes in Point Sets

Empty Monochromatic Simplices

Hamiltonian Tetrahedralizations with Steiner Points

On the Connectedness and Diameter of a Geometric Johnson Graph

On k-Convex Polygons

Token Graphs

See the researcher in context

Building this map preview

Jorge Urrutia

Research overview

Is this your work?

15 publications

Algorithms for the Euclidean Bipartite Edge Cover Problem

Convex polygons and separation of convex sets

Rectilinear Convex Hull of Points in 3D

Separating bichromatic point sets in the plane by restricted orientation convex hulls

A Note on Empty Balanced Tetrahedra in Two colored Point sets in R3\mathbb{R}^3R3

Minimizing The Maximum Distance Traveled To Form Patterns With Systems of Mobile Robots

Capturing points with a rotating polygon (and a 3D extension)

Geometric Spanning Cycles in Bichromatic Point Sets

Modem Illumination of Monotone Polygons

On kkk-Gons and kkk-Holes in Point Sets

Empty Monochromatic Simplices

Hamiltonian Tetrahedralizations with Steiner Points

On the Connectedness and Diameter of a Geometric Johnson Graph

On k-Convex Polygons

Token Graphs

See the researcher in context

Building this map preview

A Note on Empty Balanced Tetrahedra in Two colored Point sets in $\mathbb{R}^3$

On $k$ -Gons and $k$ -Holes in Point Sets