9 papers · 1 filter
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…
Computational aspects of disks enclosing many points
Prosenjit Bose, Guillermo Esteban, Tyler Tuttle
Let be a set of points in the plane. We present several different algorithms for finding a pair of points in such that any disk that contains that pair must contain at…
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…
Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs
Prosenjit Bose, Jean-Lou De Carufel, John Stuart
A Delaunay graph built on a planar point set has an edge between two vertices when there exists a disk with the two vertices on its boundary and no vertices in its interior. When t…
On geodesic disks enclosing many points
Prosenjit Bose, Guillermo Esteban, David Orden +2
Let be the largest number such that for every set of points in a polygon~, there always exist two points , where every geodesic disk contain…
Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers
Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6
Let be a set of points in , where is a constant, and let be a sequence of vertical hyperplanes that are sorted by their fi…