| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 483012 | European Journal of Operational Research | 2007 | 10 Pages |
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.
