Finding Efficient Solutions for Rectilinear Distance Location Problems Efficiently.
Abstract
Given n planar existing facility locations, a planar new facility location X is called efficient if there is no other location Y at least as close to every existing facility as X, and strictly closer than X to at least one existing facility. An algorithm is presented which is either of order n(log n) or order n (depending upon how the problem is defined) that constructs all efficient locations, and establish that no alternative algorithm can be of a low order. With the exception of two computational complexity results, this work is entirely self-conntained, and relies almost entirely upon simple geometrical analyses.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1977
- Accession Number
- ADA050165
Entities
People
- Luc G. Chalmet
- Richard L. Francis
Organizations
- University of Florida