On Geometric Algorithms that use the Furthest-Point Voronoi Diagram

Binay K. Bhattacharya, Godfried T. Toussaint

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

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.

Original languageEnglish (US)
Title of host publicationMachine Intelligence and Pattern Recognition
Pages43-61
Number of pages19
EditionC
DOIs
StatePublished - Jan 1 1985

Publication series

NameMachine Intelligence and Pattern Recognition
NumberC
Volume2
ISSN (Print)0923-0459

Keywords

  • 3.36
  • 3.63
  • 5.25
  • 5.30
  • 5.5
  • Voronoi diagram
  • algorithms
  • all-furthest-neighbor problem
  • computational geometry
  • convex hull
  • diameter
  • maximal spanning tree
  • minimum spanning circle

ASJC Scopus subject areas

  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Cite this

Bhattacharya, B. K., & Toussaint, G. T. (1985). On Geometric Algorithms that use the Furthest-Point Voronoi Diagram. In Machine Intelligence and Pattern Recognition (C ed., pp. 43-61). (Machine Intelligence and Pattern Recognition; Vol. 2, No. C). https://doi.org/10.1016/B978-0-444-87806-9.50008-6