The maximin line problem with regional demand

Given a family P={P1,…,Pm}P={P1,…,Pm} of m   polygonal regions (possibly intersecting) in the plane, we consider the problem of locating a straight line ℓ intersecting the convex hull of PP and such that mink d(Pk, ℓ) is maximal. We give an algorithm that solves the problem in time O((m2 + n log m) log n) using O(m2 + n) space, where n is the total number of vertices of P1, … , Pm. The previous best running time for this problem was O(n2) [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.