The maximin line problem with regional demand [An article from: European Journal of Operational Research] | ![The maximin line problem with regional demand [An article from: European Journal of Operational Research]](http://ecx.images-amazon.com/images/I/51G4P0G7AGL._SL160_.jpg)
 enlarge | Authors: J.m. Diaz-banez, P.a. Ramos, P. Sabariego
Publisher: Elsevier
Category: Book
Buy New: $7.95
Format: Html
Media: Digital
Pages: 9
Publication Date: August 16, 2007
Availability: Available for download now
| |
| Editorial Reviews:
Product Description
This digital document is a journal article from European Journal of Operational Research, published by Elsevier in 2007. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.
Description:
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 @? intersecting the convex hull of P and such that min"kd(P"k,@?) is maximal. We give an algorithm that solves the problem in time O((m^2+nlogm)logn) 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.
|
|
|
