arXiv preprint ·
Faster Planar Diameter using Pseudoline Envelopes
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give an improved algorithm for weighted directed planar diameter that runs in $\widetilde{O}(n^{3/2})$ time. This improves upon the $\widetilde{O}(n^{5/3})$ time algorithm for weighted directed planar diameter of Gawrychowski, Kaplan, Mozes, Sharir, and Weimann [SIAM J. Comput. 2021] and the recent $\widetilde{O}(n^{8/5})$ time algorithm for unweighted undirected planar diameter of Fredslund-Hansen, Mozes, and Weimann [SOSA 2027]. The main new result is an improved data structure for computing the farthest vertex when given feasible planar distances to the vertices on the outer face. The critical insight is the fact that normalized distances to the vertices of a face behave like pseudolines, for which we can leverage range searching and upper envelope data structures. Using the farthest vertex data structure, we are able to compute all vertex eccentricities and diameter in $\widetilde{O}(n^{3/2})$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Binary Huffman Coding with Unequal Letter Costs Is NP-Complete
Does RRT* Work on Uneven Terrain Meshes?
Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation
Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds
Constant-Round Massively Parallel Algorithms for Approximate MSTs in Metric Spaces
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.