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 -