Paper Info
Title
An Optimal Algorithm for Computing Vissible Nearest Foreign Neighbors Among Colored Line Segments
Abstract
Given a set S of n colored line segments in ℝ2 that may intersect only in endpoints. Let c(u) denote the color of a line segment u ∃ S chosen from χ ≤ n different colors. A line segment v ∃ S is a visible nearest foreign neighbor of u ∃ S if v is a nearest foreign neighbor of u in S, i.e. c(u) ≠ c(v) and no segment with a color different from c(u) is closer to u than v, and if there exist points u' ∃ u and v' ∃ v realizing the distance between u and v that are visible for each other, i.e. the open segment connecting u' and v' is not intersected by an open line segment in S. We present the first optimal θ(n log n) algorithm that computes for each line segment u ∃ S all its visible nearest foreign neighbors. The algorithm finds applications in polygon arrangement analysis, VLSI design rule checking and GIS.
Year
DOI
Venue
1998
10.1007/BFb0054355
SWAT
Keywords
Field
DocType
optimal algorithm,computing vissible nearest foreign,colored line segments,vlsi design
Discrete mathematics,Line segment,Combinatorics,Polygon,Colored,Computational geometry,Algorithm,Voronoi diagram,Time complexity,Sweep line algorithm,Mathematics,The Intersect
Conference
Volume
ISSN
ISBN
1432
0302-9743
3-540-64682-5
Citations 
PageRank 
References 
0
0.34
13
Authors
2
Name
Order
Citations
PageRank
Thorsten Graf147021.89
Kamakoti Veezhinathan2354.04