# Planar geometric location problems and maintaining the width of a planar set

Published

Conference Paper

© 1991 Association for Computing Machinery. All rights reserved. We present an O(n2 log3 n) algorithm for the two-center problem, in which we are given a set 5 of n points in the plane and wish to find two closed discs whose union contains S so that the larger of the two radii is as small as possible. We also give an O(n2 log5 n) 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. To obtain the second result, we need as a subroutine an algorithm for determining whether the width of a given set S of points in the plane ever becomes less than or equal to a given parameter W > 0, as we perform n insertions and deletions on S, and the sequence of these operations is known in advance. We present an O(n log3 n) algorithm for solving this problem.

### Duke Authors

### Cited Authors

- Agarwal, PK; Sharir, M

### Published Date

- March 1, 1991

### Published In

- Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

### Start / End Page

- 449 - 458

### International Standard Book Number 10 (ISBN-10)

- 0897913760

### Citation Source

- Scopus