Finding a Region with the Minimum Total L

1
 Distance from Prescribed Terminals

Finding a Region with the Minimum Total L 1 Distance from Prescribed Terminals

0.00 Avg rating0 Votes
Article ID: iaor20117031
Volume: 35
Issue: 3
Start Page Number: 225
End Page Number: 256
Publication Date: Mar 2003
Journal: Algorithmica
Authors: ,
Keywords: combinatorial optimization
Abstract:

Given k terminals and n axis‐parallel rectangular obstacles on the plane, our algorithm finds a plane region R* such that, for any point p in R*, the total length of the k shortest rectilinear paths connecting p and the k terminals without passing through any obstacle is minimum. The algorithm is output‐sensitive, and takes O((K+n) log n) time and O(K+n) space if k is a fixed constant, where K is the total number of polygonal vertices of the found region R*.

Reviews

Required fields are marked *. Your email address will not be published.