Planar geometric location problems
Published
Journal Article
We present an O(n2 log3n) algorithm for the two-center problem, in which we are given a set S of n points in the plane and wish to find two closed disks whose union contains S so that the larger of the two radii is as small as possible. We also give an O(n2 log5n) algorithm for solving the two-line-center problem, where we want to find two strips that cover S whose maximum width is as small as possible. The best previous solutions of both problems require O(n3) time. © 1994 Springer-Verlag New York Inc.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Sharir, M
Published Date
- February 1, 1994
Published In
Volume / Issue
- 11 / 2
Start / End Page
- 185 - 195
Electronic International Standard Serial Number (EISSN)
- 1432-0541
International Standard Serial Number (ISSN)
- 0178-4617
Digital Object Identifier (DOI)
- 10.1007/BF01182774
Citation Source
- Scopus