-
Article
Open AccessRectilinear convex hull of points in 3D and applications
Let P be a set of n points in \(\mathbb {R}^3\) R ...
-
Article
Open AccessSeparability, Boxicity, and Partial Orders
A collection \(S=\{S_i, \ldots , S_n\}\) S = {
-
Article
Minimizing Visible Edges in Polyhedra
We prove that, given a polyhedron \({\mathcal {P}}\) P in
-
Article
Open AccessSeparating 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...
-
Article
Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
Let P be a set of n points in the plane. We compute the value of \(\theta \in [0,2\pi )\) ...
-
Chapter and Conference Paper
On Geometric Graphs on Point Sets in the Plane
A graph whose vertex set is a set P of points in the plane and whose edges are line segments joining pairs of elements of P is called a geometric graph. In this paper we survey several results on geometric graphs...
-
Chapter and Conference Paper
Failure and Communication in a Synchronized Multi-drone System
A set of n drones with limited communication capacity is deployed to monitor a terrain partitioned into n pairwise disjoint closed trajectories, one per drone. In our setting, there is a communication link betwee...
-
Article
Discrete Geometry on Colored Point Sets in the Plane—A Survey
Discrete geometry on colored point sets in the plane has a long history, but this research area has been extensively developed in the last 2 decades. In 2003, a short survey entitled “Discrete geometry on red ...
-
Chapter and Conference Paper
Rectilinear Convex Hull of Points in 3D
Let P be a set of n points in \(\mathbb {R}^3\) 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)\) O ( n log n ) -time and
-
Article
On Almost Empty Monochromatic Triangles and Convex Quadrilaterals in Colored Point Sets
Let S be a set of N points on the plane in general position, colored arbitrarily with c colors (\(c\in {\mathbb {N}}\)c∈N). A subset of points is said to be monochromatic if all its points have the same color. In...
-
Article
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 poin...
-
Chapter and Conference Paper
Maximum Rectilinear Convex Subsets
Let P be a set of n points in the plane. We consider a variation of the classical Erdős-Szekeres problem, presenting efficient algorithms with \(O(n^3)\) running time and \(O(n^2)\) space complexity that compute:...
-
Article
Hamiltonian tetrahedralizations with Steiner points
A tetrahedralization of a point set in three dimensional space is the analogue of a triangulation of a point set in the plane. The dual graph of a tetrahedralization is the graph having the tetrahedra as nodes...
-
Chapter and Conference Paper
Searching for a Non-adversarial, Uncooperative Agent on a Cycle
Assume k robots are placed on a cycle–the perimeter of a unit (radius) disk–at a position of our choosing and can move on the cycle with maximum speed 1. A non-adversarial, uncooperative agent, called bus, is mov...
-
Article
Configurations of Non-crossing Rays and Related Problems
Let S be a set of n points in the plane and let R be a set of n pairwise non-crossing rays, each with an apex at a different point of S. Two sets of non-crossing rays
-
Chapter and Conference Paper
The Mathematics of Ferran Hurtado: A Brief Survey
In this paper, dedicated to our dear friend Prof. Ferran Hurtado, we survey some of the research and open problems arising from his work in collaboration with his many friends and colleagues.
-
Article
Blocking the \(k\) -Holes of Point Sets in the Plane
Let \(P\) P be ...
-
Article
Empty Monochromatic Simplices
Let S be a k-colored (finite) set of n points in \(\mathbb{R}^{d}\) , d≥3, in general position, that is, no (d+1) points...
-
Article
The Edge Rotation Graph
Let P be a set of n points on the plane in general position, n ≥ 3. The edge rotation graph $${\mathcal{E} \mathcal{R} \mathcal{G}(P,...
-
Chapter and Conference Paper
Complexity of Barrier Coverage with Relocatable Sensors in the Plane
We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in...
