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