Let $P$ be a simple polygon with $m$ vertices. After $O(m)$‑time preprocessing of $P$, any set $S$ of $n$ additively weighted point sites can be processed in $O(n\log n + n\log^2 m)$ time to obtain an implicit additively weighted geodesic Voronoi diagram, supporting nearest‑neighbor queries in $O(\log (n+m))$ time. Explicit construction would require $\Omega(m)$ time. We introduce a new sweep‑line paradigm that avoids building the diagram explicitly and a novel point‑location technique for implicit subdivisions.
Using this framework we obtain dynamic data structures for weighted geodesic nearest‑neighbor searching and the first efficient algorithms for shortest paths in geodesic disk graphs. After the same $O(m)$ preprocessing, single‑source shortest paths in an unweighted geodesic disk graph of $n$ sites run in $O(n\log n + n\log^2 m)$ time, while the weighted case runs in $O(n^{3/2}(\log n + \log^2 m))$ time. The approach also extends to implicit farthest geodesic Voronoi diagrams for unweighted sites, yielding analogous bounds and dynamic farthest‑neighbor structures.
Review: By leveraging implicit representations and a novel sweep‑line scheme, the paper reduces the overhead of constructing weighted Voronoi diagrams inside complex polygons and delivers practical dynamic solutions for nearest‑neighbor and shortest‑path queries in geometric networks.