设 $P$ 为一个有 $m$ 条边的简单多边形。对 $P$ 进行 $O(m)$ 时间的预处理后，任意 $n$ 个加权点集 $S$ 可以在 $O(n\log n + n\log^2 m)$ 时间内构造出隐式加权几何Voronoi图，并支持 $O(\log (n+m))$ 时间的最近邻查询。显式构造该图至少需要 $\Omega(m)$ 时间。我们提出了一种新的扫描线范式，避免了显式构造过程，并引入了一种在隐式细分中进行点定位的技术。
基于该框架，可构建动态数据结构用于加权几何最近邻搜索，并首次实现了在几何盘图中求最短路径的高效算法。相同的 $O(m)$ 预处理后，单源最短路在无权情况下的时间复杂度为 $O(n\log n + n\log^2 m)$，在加权情况下为 $O(n^{3/2}(\log n + \log^2 m))$。我们同样将技术推广到无权点的隐式最远几何Voronoi图，得到相似的时间界限并支持动态最远邻查询。
点评：该工作通过隐式表示和新颖的扫描线策略，显著降低了在复杂多边形内部构建加权Voronoi图的开销，为几何网络中的最近邻和最短路问题提供了实用的动态解法。