5 papers
On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets
Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari +3
The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an ear…
The Volume Helly Theorem in the plane, colorful version
Imre Bárány, Bobby Miraftab, Leonidas Theocharous
We prove a colorful volume Helly theorem for convex sets in : There is a constant such that if are fini…
On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons
Mark de Berg, Prosenjit Bose, Leonidas Theocharous
Many algorithmic problems can be solved (almost) as efficiently in metric spaces of bounded doubling dimension as in Euclidean space. Unfortunately, the metric space defined by poi…
Realizing Metric Spaces with Convex Obstacles
Sándor Kisfaludi-Bak, Leonidas Theocharous
The presence of obstacles has a major impact on distance computation, motion planning, and visibility. While these problems are well studied in the plane, our understanding in thre…
An Improved Bound for Plane Covering Paths
Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz +8
A covering path for a finite set of points in the plane is a polygonal path such that every point of lies on a segment of the path. The vertices of the path need not be at…