The maximin line problem with regional demand

Given a family P = {P-1,..., P-m} of m polygonal regions (possibly intersecting) in the plane, we consider the problem of locating a straight line 2 intersecting the convex hull of 9 and such that min(k) d(P-k, l) is maximal. We give an algorithm that solves the problem in time O((m(2) + n log m) log n) using O(m(2) + n) space, where n is the total number of vertices of P-1,..., P-m. The previous best running time for this problem was O(n(2)) [J. Janardan, F.P. Preparata, Widest-corridor problems, Nordic Journal of Computing 1 (1994) 231-245]. We also improve the known complexity for several variants of this problem which include a three dimensional version - the maximin plane problem -, the weighted problem and considering measuring distance different to the Euclidean one. (c) 2006 Elsevier B.V. All rights reserved.