Planar geometric location problems and maintaining the width of a planar set
© 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.
Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Start / End Page
International Standard Book Number 10 (ISBN-10)