Given a set S of n colored line segments in IR~2 that may intersect only in endpoints. Let c(u) denote the color of a line segment u #epsilon# S chosen from X<=n different colors. A line segment v #epsilon# S is a visible nearest foreign neighbor of u #epsilon# S if v is a nearest foreign neighbor of u in S, i.e. c(u) not=c(v) and no segment with a color different from c(u) is closer to u than v, and if there exist points umin #epsilon# u and vmin v realizing the distance between u and v that are visible for each other, i.e. the open segment connecting umin and vmin is not intersected by an open line segment in S. We present the first optimal #THETA#(n log n) algorithm that computes for each line segment u #epsilon# S all its visible nearest foreign neighbors. The algorithm finds applications in polygon arrangement analysis, VLSI design rule checking and GIS.
展开▼
