کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
483012 | 1446194 | 2007 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The maximin line problem with regional demand The maximin line problem with regional demand](/preview/png/483012.png)
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.
Journal: European Journal of Operational Research - Volume 181, Issue 1, 16 August 2007, Pages 20–29