Metraipolis › archive › dc_142a5bdd2cd5
Implicit Additively Weighted Geodesic Voronoi Diagrams and Applications — arXiv:2610.42075
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.42075
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T08:24:12.110Z
- SHA-256 of the archived text
1885d9d27aa40f2b131d91189dc13e9370448dbf68ea2d9ae639d8cd8389e31d- Stable URL of this page
https://metraipolis.com/documento/dc_142a5bdd2cd5
How to cite
Implicit Additively Weighted Geodesic Voronoi Diagrams and Applications — arXiv:2610.42075 — arXiv (en), https://arxiv.org/abs/2610.42075 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_142a5bdd2cd5 (Metraipolis archive dc_142a5bdd2cd5, sha256 1885d9d27aa40f2b131d91189dc13e9370448dbf68ea2d9ae639d8cd8389e31d)
BibTeX
@misc{dc142a5bdd2cd5,
title = {Implicit Additively Weighted Geodesic Voronoi Diagrams and Applications — arXiv:2610.42075},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.42075},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_142a5bdd2cd5; sha256 1885d9d27aa40f2b131d91189dc13e9370448dbf68ea2d9ae639d8cd8389e31d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42075. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Let $P$ be a simple polygon with $m$ vertices. After $O(m)$-time preprocessing of $P$, for any set $S$ of $n$ additively weighted point sites, we compute an implicit additively weighted geodesic Voronoi diagram in $O(n\log n+n\log^2 m)$ time, supporting nearest-neighbor queries in $O(\log(n+m))$ time. In contrast, explicitly constructing the diagram requires $\Omega(m)$ time. Our algorithm introduces a new sweep-line paradigm that avoids explicitly constructing the diagram, together with a novel technique for point location in implicit subdivisions. As applications, we obtain new dynamic data structures for additively weighted geodesic nearest-neighbor searching and the first efficient algorithms for shortest paths in geodesic disk graphs. After the same $O(m)$-time preprocessing, single-source shortest paths in a geodesic disk graph of $n$ sites can be computed in $O(n\log n+n\log^2 m)$ time in the unweighted case and $O(n^{3/2}(\log n+\log^2 m))$ time in the weighted case. We also extend our techniques to implicit farthest geodesic Voronoi diagrams for unweighted sites, obtaining analogous bounds and dynamic farthest-neighbor data structures.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Computational Geometry (cs.CG) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.42075 — 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-03T08:07:53.823Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).