9 papers
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…
New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
Aritra Banik, Sayani Das, Anil Maheshwari +6
In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph , consisting of a vertex set of size and an edge set .…
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…
Contiguous Boundary Guarding
Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell +3
We study the problem of guarding the boundary of a simple polygon with a minimum number of guards such that each guard covers a contiguous portion of the boundary. First, we presen…