{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:08:26Z","timestamp":1761620906921},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1986,11,1]],"date-time":"1986-11-01T00:00:00Z","timestamp":531187200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1986,11]]},"DOI":"10.1007\/bf01840442","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T21:29:13Z","timestamp":1121290153000},"page":"193-211","source":"Crossref","is-referenced-by-count":86,"title":["Geometric complexity of some location problems"],"prefix":"10.1007","volume":"1","author":[{"given":"D. T.","family":"Lee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y. F.","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01840442_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley; Reading, MA, 1974."},{"key":"BF01840442_CR2","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. Lower bounds for algebraic computation trees,Proc. 15th Annual Symp. on Theory of Computing, 1983, pp. 80\u201386.","DOI":"10.1145\/800061.808735"},{"key":"BF01840442_CR3","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","volume":"18","author":"P. Dobkin","year":"1979","unstructured":"P. Dobkin and R. J. Lipton. On the complexity of computations under varying sets of primitives,J. Comput. System Sci. 18 (1979), 86\u201391.","journal-title":"J. Comput. System Sci."},{"key":"BF01840442_CR4","first-page":"485","volume-title":"tRegional Science and Urban Economics, Vol. 12","author":"Z. Drezner","year":"1982","unstructured":"Z. Drezner. Competitive location strategies for two facilities. In: tRegional Science and Urban Economics, Vol. 12, Elsevier: North-Holland, 1982, pp. 485\u2013493."},{"key":"BF01840442_CR5","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision.SIAM J. Comput. (to appear).","DOI":"10.1137\/0215023"},{"key":"BF01840442_CR6","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1287\/trsc.6.4.379","volume":"6","author":"J. Elzinga","year":"1972","unstructured":"J. Elzinga and D. W. Hearn. Geometrical solutions for some minimax location problems.Transportation Sci.,6 (1972), 379\u2013394.","journal-title":"Transportation Sci."},{"issue":"7","key":"BF01840442_CR7","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1145\/359545.359553","volume":"21","author":"M. L. Fredman","year":"1978","unstructured":"M. L. Fredman and B. Weide. On the complexity of computing the measure of U[a i,b i],Commun. ACM,21, 7 (July 1978), 540\u2013544.","journal-title":"Commun. ACM"},{"key":"BF01840442_CR8","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham. An efficient algorithm for determining the convex hull of a finite set.Inform. Process. Lett,1 (1972), 132\u2013133.","journal-title":"Inform. Process. Lett"},{"key":"BF01840442_CR9","volume-title":"\u201cOn locating new facilities in a competitive environment,\u201dISOLDE II","author":"S. L. Hakimi","year":"1981","unstructured":"S. L. Hakimi. \u201cOn locating new facilities in a competitive environment,\u201dISOLDE II, June 1981, Skodsberg, Denmark."},{"key":"BF01840442_CR10","doi-asserted-by":"crossref","unstructured":"M. E. Houle and G. T. Toussaint. Computing the width of a set,ACM Symp. on Computational Geometry, Baltimore, Maryland, 1985, pp. 1\u20137.","DOI":"10.1145\/323233.323234"},{"issue":"1","key":"BF01840442_CR11","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. G. Kirkpatrick","year":"1983","unstructured":"D. G. Kirkpatrick. Optimal search in planar subdivisions.SIAM J. Comput. 12, 1 (Feb. 1983), 28\u201335.","journal-title":"SIAM J. Comput."},{"key":"BF01840442_CR12","unstructured":"D. T. Lee. Farthest neighbor Voronoi diagrams and applications. Tech. Rep. #80-11-FC-04, Dept. EE\/CS, Northwestern University, Nov. 1980."},{"issue":"4","key":"BF01840442_CR13","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/0020-0190(79)90066-8","volume":"9","author":"D. T. Lee","year":"1979","unstructured":"D. T. Lee and C. C. Yang. Location of multiple points in a planar subdivision,Inform. Process. Lett. 9, 4 (Nov. 1979), 190\u2013192.","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"BF01840442_CR14","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/3828.3838","volume":"32","author":"U. Manber","year":"1985","unstructured":"U. Manber and M. Tompa. The complexity of problems on probabilistic, nondeterministic and alternating decision trees.J. ACM 32, 3 (1985), 720\u2013732.","journal-title":"J. ACM"},{"issue":"4","key":"BF01840442_CR15","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems,SIAM J. Comput.,12, 4 (1983), 759\u2013776.","journal-title":"SIAM J. Comput."},{"key":"BF01840442_CR16","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N. Megiddo","year":"1982","unstructured":"N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane,Oper. Res. Lett. 1 (1982), 194\u2013197.","journal-title":"Oper. Res. Lett."},{"key":"BF01840442_CR17","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/0377-2217(83)90183-2","volume":"12","author":"J. G. Morris","year":"1983","unstructured":"J. G. Morris and J. P. Norback. Linear facility location-Solving extensions of the basic problem.European J. Oper. Res.,12, (1983), 90\u201394.","journal-title":"European J. Oper. Res."},{"issue":"4","key":"BF01840442_CR18","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1137\/0208043","volume":"8","author":"F. P. Preparata","year":"1979","unstructured":"F. P. Preparata. A note on locating a set of points in a planar subdivision.SIAM J. Comput.,8, 4 (1979), 542\u2013545.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"BF01840442_CR19","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"F. P. Preparata","year":"1977","unstructured":"F. P. Preparata and S. J. Hong. Convex hulls of finite sets of points in two and three dimensions.Commun. ACM,20, 2 (1977), 87\u201393.","journal-title":"Commun. ACM"},{"issue":"4","key":"BF01840442_CR20","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1145\/321724.321730","volume":"19","author":"E. M. Reingold","year":"1972","unstructured":"E. M. Reingold. On the optimality of some set algorithms,J. ACM,19, 4 (1972), 649\u2013659.","journal-title":"J. ACM"},{"key":"BF01840442_CR21","volume-title":"Problems in computational geometry","author":"M. I. Shamos","year":"1975","unstructured":"M. I. Shamos. Problems in computational geometry, Dept. Comput. Sci., Yale University: New Haven, CO, May 1975."},{"key":"BF01840442_CR22","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey. Closest-point problems.Proc. IEEE 16th Symp. Foundations of Comput. Sci., 1975, pp. 151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"BF01840442_CR23","unstructured":"G. T. Toussaint. Solving geometric problems with the rotating calipers.Proc. of IEEE MELECON, Athens, Greece, 1983."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840442.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840442\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840442","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T06:58:55Z","timestamp":1586329135000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840442"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":23,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["BF01840442"],"URL":"https:\/\/doi.org\/10.1007\/bf01840442","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}