### 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 language | English (US) |
---|---|

Title of host publication | Machine Intelligence and Pattern Recognition |

Pages | 43-61 |

Number of pages | 19 |

Edition | C |

DOIs | |

State | Published - Jan 1 1985 |

### Publication series

Name | Machine Intelligence and Pattern Recognition |
---|---|

Number | C |

Volume | 2 |

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

*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