TY - CHAP
T1 - On Geometric Algorithms that use the Furthest-Point Voronoi Diagram
AU - Bhattacharya, Binay K.
AU - Toussaint, Godfried T.
PY - 1985/1/1
Y1 - 1985/1/1
N2 - In this paper it is shown that the diameter D(P) of a set of n points P on the plane is not necessarily an edge in the dual of the furthest-point Voronoi diagram (FPVD) of P, as previously claimed in [1] and [2]. It is also proved that if P is contained in the disk determined by D(P) then the above property does hold. Furthermore, it is shown that an edge e in the dual of the FPVD(P) intersects its corresponding edge in the FPVD(P) if, and only if, P is contained in the disk determined by e. These results invalidate several algorithms for solving the diameter, all-furthest-neighbor, and maximal spanning tree problems proposed in [1] and [2]. A proof of correctness is given for the minimum spanning circle algorithm proposed in [2] and [3]. Finally new O(n log n) algorithms are offered for the minimum spanning circle and all-furthest-neighbor problems.
AB - In this paper it is shown that the diameter D(P) of a set of n points P on the plane is not necessarily an edge in the dual of the furthest-point Voronoi diagram (FPVD) of P, as previously claimed in [1] and [2]. It is also proved that if P is contained in the disk determined by D(P) then the above property does hold. Furthermore, it is shown that an edge e in the dual of the FPVD(P) intersects its corresponding edge in the FPVD(P) if, and only if, P is contained in the disk determined by e. These results invalidate several algorithms for solving the diameter, all-furthest-neighbor, and maximal spanning tree problems proposed in [1] and [2]. A proof of correctness is given for the minimum spanning circle algorithm proposed in [2] and [3]. Finally new O(n log n) algorithms are offered for the minimum spanning circle and all-furthest-neighbor problems.
KW - 3.36
KW - 3.63
KW - 5.25
KW - 5.30
KW - 5.5
KW - Voronoi diagram
KW - algorithms
KW - all-furthest-neighbor problem
KW - computational geometry
KW - convex hull
KW - diameter
KW - maximal spanning tree
KW - minimum spanning circle
UR - http://www.scopus.com/inward/record.url?scp=85012589136&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85012589136&partnerID=8YFLogxK
U2 - 10.1016/B978-0-444-87806-9.50008-6
DO - 10.1016/B978-0-444-87806-9.50008-6
M3 - Chapter
AN - SCOPUS:85012589136
T3 - Machine Intelligence and Pattern Recognition
SP - 43
EP - 61
BT - Machine Intelligence and Pattern Recognition
ER -