5 papers · 1 filter
The Road to the Closest Point is Paved by Good Neighbors
Sariel Har-Peled, Benjamin Raichel, Eliot W. Robson
Given a set of points in , and a parameter , we present a new construction of a directed graph , of size $O…
Well-Separated Pairs Decomposition Revisited
Sariel Har-Peled, Benjamin Raichel, Eliot W. Robson
We revisit the notion of WSPD (i.e., well-separated pairs-decomposition), presenting a new construction of WSPD for any finite metric space, and show that it is asymptotically inst…
Improving the average dilation of a metric graph by adding edges
Sariel Har-Peled, Eliot W. Robson
For a graph spanning a metric space, the dilation of a pair of points is the ratio of their distance in the shortest path graph metric to their distance in the metric space. Gi…
The Analytic Arc Cover Problem and its Applications to Contiguous Art Gallery, Polygon Separation, and Shape Carving
Eliot W. Robson, Jack Spalding-Jamieson, Da Wei Zheng
We show the following problems are in : 1. The contiguous art gallery problem -- a variation of the art gallery problem where each guard can protect a contiguous interv…
Sparsifying Disk Intersection Graphs for Reliable Connectivity
Sariel Har-Peled, Eliot Wong Robson
The intersection graph induced by a set $\Disks$ of disks can be dense. It is thus natural to try and sparsify it, while preserving connectivity. Unfortunately, sparse graphs c…