Source author record

Carlos Seara

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 Computational Complexity

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Center of maximum-sum matchings of bichromatic points

Let $R$ and $B$ be two disjoint point sets in the plane with $|R|=|B|=n$ . Let $\mathcal{M}=\{(r_i,b_i),i=1,2,\ldots,n\}$ be a perfect matching that matches points of $R$ with points of $B$ and maximizes $\sum_{i=1}^n\|r_i-b_i\|$ , the total Euclidean distance of the matched pairs. In this paper, we prove that there exists a point $o$ of the plane (the center of $\mathcal{M}$ ) such that $\|r_i-o\|+\|b_i-o\|\le \sqrt{2}~\|r_i-b_i\|$ for all $i\in\{1,2,\ldots,n\}$ .

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

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.

preprint2014arXiv

New results on stabbing segments with a polygon

We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon $\mathcal{P}$ if at least one of its two endpoints is contained in $\mathcal{P}$ . A segment set $S$ is stabbed by $\mathcal{P}$ if every segment of $S$ is stabbed by $\mathcal{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.

preprint2007arXiv

Extremal Graph Theory for Metric Dimension and Diameter

A set of vertices $S$ \emph{resolves} a connected graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$ . The \emph{metric dimension} of $G$ is the minimum cardinality of a resolving set of $G$ . Let $\mathcal{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 $\mathcal{G}_{β,D}$ is exactly $β+D$ . The first contribution of this paper is to characterise the graphs in $\mathcal{G}_{β,D}$ with order $β+D$ for all values of $β$ and $D$ . Such a characterisation was previously only known for $D\leq2$ or $β\leq1$ . The second contribution is to determine the maximum order of a graph in $\mathcal{G}_{β,D}$ for all values of $D$ and $β$ . Only a weak upper bound was previously known.

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.