期刊
ALGORITHMICA
卷 74, 期 1, 页码 415-439出版社
SPRINGER
DOI: 10.1007/s00453-014-9950-0
关键词
Computational geometry; Voronoi diagram; Line segments; Planar straight line graph; Order-k Voronoi diagram; k nearest neighbors; L-p metric
资金
- Swiss National Science Foundation [SNF 200021-127137]
- ESF EUROCORES program EuroGIGA/VORONOI [SNF 20GG21-134355]
The order- Voronoi diagram of line segments has properties surprisingly different from its counterpart for points. For example, a single order- Voronoi region may consist of disjoint faces. In this paper, we analyze the structural properties of this diagram and show that its combinatorial complexity is , for non-crossing line segments, despite the presence of disconnected regions. The same bound holds for intersecting line segments, for . We also consider the order- Voronoi diagram of line segments that form a planar straight-line graph, and augment the definition of an order- diagram to cover sites that are not disjoint. On the algorithmic side, we extend the iterative approach to construct this diagram, handling complications caused by the presence of disconnected regions. All bounds are valid in the general metric, . For non-crossing segments in the and metrics, we show a tighter bound for k > n/2.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据