ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

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

Kusakari, Yoshiyuki ; Nishizeki, Takao

Springer

Algorithmica 35 (NaN), S. 225-256

add to mindlist on the mindlist

Details

ISSN: 1432-0541

Keywords: Key words. Facility location, Optimal region, Rectilinear shortest path, L1 distance.

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: 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 * .

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/s00453-002-0997-y

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit