10 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…
A Clique-Based Separator for Intersection Graphs of Geodesic Disks in
Boris Aronov, Mark de Berg, Leonidas Theocharous
Let be a (well-behaved) shortest-path metric defined on a path-connected subset of and let be a set of geodesic disks with respe…
A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon
Mark de Berg, Leonidas Theocharous
Let be a simple polygon with vertices and let be a set of points inside . We prove that there exists, for any , a set $\mathca…
Clustering with Few Disks to Minimize the Sum of Radii
Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer +2
Given a set of points in the Euclidean plane, the -MinSumRadius problem asks to cover this point set using disks with the objective of minimizing the sum of the radii of…
Clique-Based Separators for Geometric Intersection Graphs
Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh +1
Let be a set of objects in the plane and let be its intersection graph. A balanced clique-based separator of is a set consisting of cliques whose removal…
Grid Drawings of Graphs with Constant Edge-Vertex Resolution
Michael A. Bekos, Martin Gronemann, Fabrizio Montecchiani +3
We study the algorithmic problem of computing drawings of graphs in which each vertex is a disk with fixed radius , each edge is a straight-line segment connecting…