Metraipolis › archive › dc_a2a5affeca45

Faster Planar Diameter using Pseudoline Envelopes — arXiv:2611.05019

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05019
License (as archived)
CC0-1.0
Archived
2026-11-04T12:59:23.448Z
SHA-256 of the archived text
ca3e48de0a62fb3a00b35472940e4901f5cb409ced06a3ac210abce4d7abd877
Stable URL of this page
https://metraipolis.com/documento/dc_a2a5affeca45

How to cite

Faster Planar Diameter using Pseudoline Envelopes — arXiv:2611.05019 — arXiv (en), https://arxiv.org/abs/2611.05019 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a2a5affeca45 (Metraipolis archive dc_a2a5affeca45, sha256 ca3e48de0a62fb3a00b35472940e4901f5cb409ced06a3ac210abce4d7abd877)
BibTeX
@misc{dca2a5affeca45,
  title = {Faster Planar Diameter using Pseudoline Envelopes — arXiv:2611.05019},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05019},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a2a5affeca45; sha256 ca3e48de0a62fb3a00b35472940e4901f5cb409ced06a3ac210abce4d7abd877},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05019. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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})$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Geometry (cs.CG).
Pagina del lavoro: https://arxiv.org/abs/2611.05019 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T12:35:02.326Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).