Geometric complexity of some location problems. (English) Zbl 0639.68038
Given a set of n demand points with weight \(w_ i\), \(i=1,2,...,n\), in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An \(\Omega\) (n log n) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0326.68005 |
| [2] | M. Ben-Or. Lower bounds for algebraic computation trees,Proc. 15th Annual Symp. on Theory of Computing, 1983, pp. 80-86. |
| [3] | Dobkin, P.; Lipton, R. J., On the complexity of computations under varying sets of primitives, J. Comput. System Sci., 18, 86-91 (1979) · Zbl 0409.68023 · doi:10.1016/0022-0000(79)90054-0 |
| [4] | Drezner, Z., Competitive location strategies for two facilities, tRegional Science and Urban Economics, Vol. 12, 485-493 (1982), North-Holland: Elsevier, North-Holland |
| [5] | H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision.SIAM J. Comput. (to appear). · Zbl 0602.68102 |
| [6] | Elzinga, J.; Hearn, D. W., Geometrical solutions for some minimax location problems, Transportation Sci., 6, 379-394 (1972) · doi:10.1287/trsc.6.4.379 |
| [7] | Fredman, M. L.; Weide, B., On the complexity of computing the measure of U[a_i,b_i], Commun. ACM, 21, 7, 540-544 (1978) · Zbl 0378.68032 · doi:10.1145/359545.359553 |
| [8] | Graham, R. L., An efficient algorithm for determining the convex hull of a finite set, Inform. Process. Lett, 1, 132-133 (1972) · Zbl 0236.68013 · doi:10.1016/0020-0190(72)90045-2 |
| [9] | Hakimi, S. L., “On locating new facilities in a competitive environment,”ISOLDE II (1981), Denmark: Skodsberg, Denmark |
| [10] | M. E. Houle and G. T. Toussaint. Computing the width of a set,ACM Symp. on Computational Geometry, Baltimore, Maryland, 1985, pp. 1-7. |
| [11] | Kirkpatrick, D. G., Optimal search in planar subdivisions, SIAM J. Comput., 12, 1, 28-35 (1983) · Zbl 0501.68034 · doi:10.1137/0212002 |
| [12] | D. T. Lee. Farthest neighbor Voronoi diagrams and applications. Tech. Rep. #80-11-FC-04, Dept. EE/CS, Northwestern University, Nov. 1980. |
| [13] | Lee, D. T.; Yang, C. C., Location of multiple points in a planar subdivision, Inform. Process. Lett., 9, 4, 190-192 (1979) · doi:10.1016/0020-0190(79)90066-8 |
| [14] | Manber, U.; Tompa, M., The complexity of problems on probabilistic, nondeterministic and alternating decision trees, J. ACM, 32, 3, 720-732 (1985) · Zbl 0631.68044 · doi:10.1145/3828.3838 |
| [15] | Megiddo, N., Linear-time algorithms for linear programming in R^3 and related problems, SIAM J. Comput., 12, 4, 759-776 (1983) · Zbl 0521.68034 · doi:10.1137/0212052 |
| [16] | Megiddo, N.; Tamir, A., On the complexity of locating linear facilities in the plane, Oper. Res. Lett., 1, 194-197 (1982) · Zbl 0507.90025 · doi:10.1016/0167-6377(82)90039-6 |
| [17] | Morris, J. G.; Norback, J. P., Linear facility location-Solving extensions of the basic problem, European J. Oper. Res., 12, 90-94 (1983) · Zbl 0499.90025 · doi:10.1016/0377-2217(83)90183-2 |
| [18] | Preparata, F. P., A note on locating a set of points in a planar subdivision, SIAM J. Comput., 8, 4, 542-545 (1979) · Zbl 0421.68046 · doi:10.1137/0208043 |
| [19] | Preparata, F. P.; Hong, S. J., Convex hulls of finite sets of points in two and three dimensions, Commun. ACM, 20, 2, 87-93 (1977) · Zbl 0342.68030 · doi:10.1145/359423.359430 |
| [20] | Reingold, E. M., On the optimality of some set algorithms, J. ACM, 19, 4, 649-659 (1972) · Zbl 0246.68008 · doi:10.1145/321724.321730 |
| [21] | Shamos, M. I., Problems in computational geometry (1975), New Haven, CO: Dept. Comput. Sci., Yale University, New Haven, CO |
| [22] | M. I. Shamos and D. Hoey. Closest-point problems.Proc. IEEE 16th Symp. Foundations of Comput. Sci., 1975, pp. 151-162. |
| [23] | G. T. Toussaint. Solving geometric problems with the rotating calipers.Proc. of IEEE MELECON, Athens, Greece, 1983. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
