11 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…
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…
Completely Independent Steiner Trees
Anil Maheshwari, Karthik Murali, Michiel Smid
Spanning trees are fundamental for efficient communication in networks. For fault-tolerant communication, it is desirable to have multiple spanning trees to ensure resilience again…
Linear-Time -Approximation Algorithms for Two-Line-Center Problems
Chaeyoon Chung, Anil Maheshwari, Michiel Smid
Given a set of points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in to its closest line. W…
Noncrossing Longest Paths and Cycles
Greg Aloupis, Ahmad Biniaz, Prosenjit Bose +7
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short…
Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +1
Let be an edge-weighted graph, and let be a subgraph of . We say that is an -fault-tolerant -spanner for , if the following is true for any subset of at…