Abstract
In this paper we study the following general MaxMinoptimization problem concerning undesirable (obnoxious) facility location: Given a set of n sites S inside a convex region P, construct m garbage deposit sites V m such that the minimum distance between these sites V m and the union of S and V m , V m ∪S, is maximized. We present a general method using Voronoi diagrams to approximately solve two such problems when the sites S’s are points and weighted convex polygons (correspondingly, V m’s are points and weighted points and the distances are L 2 and weighted respectively). In the latter case we generalize the Voronoi diagrams for disjoint weighted convex polygons in the plane. Our algorithms run in polynomial time and approximate the optimal solutions of the above two problems by a factor of 2.
The authors would like to acknowledge the support of research grants from NSF of China, Research Grants Council of Hong Kong SAR, China (CERG Project No. CityU1103/99E) and City University of Hong Kong
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
F. Aurenhammer, Voronoi diagrams: a survey of a fundamental geometric data structures, ACM Comput. Surveys, 23(3), pp. 343–405, 1991.
F. Aurenhammer and H. Edelsbrunner, An optimal algorithm for constructing the weighted Voronoi diagram in the plane, Pattern Recognition, 17, pp. 251–257, 1984.
J. Boissonnat, O. Devillers, R. Schott, M. Teillaud and M. Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Disc. Comp. Geom. 8, pp. 51–71, 1992.
O. Devillers, S. Meiser and M. Teillaud, Fully dynamic Delaunay triangulation in logarithmic expected time per operation, Comp. Geom. Theory and Appl. 2, pp. 55–80, 1992.
L. Devroye, E. Mücke and B. Zhu, A note on point location in Delaunay triangulations of random points, Algorithmica, special issue on Average Case Analysis of Algorithms, 22(4), pp. 477–482, Dec, 1998.
T. Feder and D. Greene, Optimal algorithms for approximate clustering, Proc. 20th STOC, pp. 434–444, 1988.
L. Guibas, D. Knuth and M. Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica, 7, pp. 381–413, 1992.
T. Gonzalez, Clustering to minimize the maximum intercluster distance, Theo. Comput. Sci., 38, pp. 293–306, 1985.
R. Klein, K. Mehlhorn and S. Meiser, Randomized incremental construction of abstract Voronoi diagrams, Comp. Geom. Theory and Appl. 3, pp. 157–184, 1993.
D.T. Lee and C.K. Wong, Voronoi diagrams in the L1 (L∞) metric with twodimensional storage applications, SIAM. J Comput., 9, pp. 200–211, 1980.
D.T. Lee, Two-dimensional Voronoi diagrams in the L p metric, J. ACM, 27, pp. 604–618, 1980.
E. Mücke, I. Saias and B. Zhu, Fast Randomized Point Location Without Preprocessing in Two and Three-dimensional Delaunay Triangulations, Comp. Geom. Theory and Appl, special issue for SoCG’96, 12(1/2), pp. 63–83, Feb, 1999.
K. Nurmela and P. Ostergard, Packing up to 50 equal circles in a square, Disc. Comp. Geom. 18, pp. 111–120, 1997.
F. Preparata and M. Shamos, Computational Geometry, Springer-Verlag, 1985.
P. Widmayer, Y.F. Wu, and C.K. Wong, On some distance problems in fixed orientations. SIAM J. Comput., 16, pp. 728–746, 1987.
C.K. Yap, An O(n log n) algorithm for the Voronoi diagram of a set of curve segment, Disc. Comp. Geom. 2, pp. 365–393, 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Qin, Z., Xu, Y., Zhu, B. (2000). On Some Optimization Problems in Obnoxious Facility Location. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_32
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_32
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive