Abstract
We develop efficient algorithms for locating an obnoxious facility in a simple polygonal region and for locating a desirable facility in a simple polygonal region. Many realistic facility location problems require the facilities to be constrained to lie in a simple polygonal region. Given a set S of m demand points and a simple polygon R of n vertices, we first show how to compute the location of an obnoxious facility constrained to lie in R, in O((m + n) log m + m log n) time. We then show how to compute the location of a desirable facility constrained to lie in R, also in O((m + n) log m + m log n) time. Both running times are an improvement over the known algorithms in the literature. Finally, our results generalize to the setting where the facility is constrained to lie within a set of simple polygons as opposed to a single polygon at a slight increase in complexity.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. Bose and G. T. Toussaint. Computing the constrained euclidean, geodesic and link centers of a simple polygon with applications. Studies of Location Analysis, Special Issue on Computational Geometry, 15:37–66, 2000.
H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM J. Comput., 15:317–340, 1986.
D. Halperin and C. Linhart. The smallest enclosing disks with obstacles. Manuscript, Dep. of Comp. Science, Tel-Aviv University, Israel, 1999.
J. Hershberger and S. Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. Journal of Algorithms, 18(3):403–431, 1995.
D. Halperin, M. Sharir, and K. Goldberg. The 2-center problem with obstacles. In Proc. of the 16th ACM Symp. on Comp. Geom., pages 80–90, 2000.
F. Hurtado, V. Sacristn, and G. Toussaint. Constrained facility location. Studies of Location Analysis, Special Issue on Computational Geometry, 15:17–35, 2000.
D. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12(1):28–35, 1983.
N. Megiddo. Linear-time algorithms for linear programming in r3 and related problems. SIAM J. Comput., 12:759–776, 1983.
F. P. Preparata and M. I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, 1985.
G. T. Toussaint. Computing largest empty circles with location constraints. Int. J. of Comp. and Information Science, 12(5):347–358, 1983.
Q. Wang. Facility Location Constrained to a Simple Polygon. Master’s thesis, Carleton University, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bose, P., Wang, Q. (2002). Facility Location Constrained to a Polygonal Domain. In: Rajsbaum, S. (eds) LATIN 2002: Theoretical Informatics. LATIN 2002. Lecture Notes in Computer Science, vol 2286. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45995-2_18
Download citation
DOI: https://doi.org/10.1007/3-540-45995-2_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43400-9
Online ISBN: 978-3-540-45995-8
eBook Packages: Springer Book Archive