{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:11:33Z","timestamp":1725455493188},"publisher-location":"Berlin\/Heidelberg","reference-count":35,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540167838"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0016240","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T05:39:17Z","timestamp":1131860357000},"page":"154-167","source":"Crossref","is-referenced-by-count":5,"title":["Geometric location problems and their complexity"],"prefix":"10.1007","author":[{"given":"D. T.","family":"Lee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA., 1974."},{"doi-asserted-by":"crossref","unstructured":"Atallah, M. and G. Frederickson, \"A note on finding a maximum empty rectangle,\" Discrete Applied Math., to appear.","key":"11_CR2","DOI":"10.1016\/0166-218X(86)90071-5"},{"doi-asserted-by":"crossref","unstructured":"Ben-Or, M, \"Lower bounds for algebraic computation trees,\" Proc. 15th ACM Annual Symp. on Theory of Comput., (Apr. 1983) 80\u201386.","key":"11_CR3","DOI":"10.1145\/800061.808735"},{"issue":"1","key":"11_CR4","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0215022","volume":"15","author":"B.M. Chazelle","year":"1986","unstructured":"Chazelle, B.M., R.L. Drysdale III, and D.T. Lee, \"Computing the largest empty rectangle,\" SIAM J. Comput., 15,1 (Feb. 1986), 300\u2013315.","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"11_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02238188","volume":"36","author":"B.M. Chazelle","year":"1986","unstructured":"Chazelle, B.M. and D.T. Lee, \"On a circle placement problem,\" Computing, 36(1\u20132), 1986, 1\u201316.","journal-title":"Computing"},{"unstructured":"Cole, R., \"Slowing down sorting networks to obtain faster sorting algorithms,\" Tech. Rep. 117, Dept. of Comput. Sci., Courant Inst. of Math. Sci., April 1984.","key":"11_CR6"},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1287\/mnsc.27.7.848","volume":"27","author":"Z. Drezner","year":"1981","unstructured":"Drezner, Z., \"On a modified 1-center problem,\" Management Sci., 27 (1981) 838\u2013851.","journal-title":"Management Sci."},{"key":"11_CR8","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/0166-0462(82)90003-5","volume":"12","author":"Z. Drezner","year":"1982","unstructured":"Drezner, Z., \"Competitive location strategies for two facilities,\" Regional Science and Urban Economics, 12, 1982, 485\u2013493.","journal-title":"Regional Science and Urban Economics"},{"doi-asserted-by":"crossref","unstructured":"Drezner, Z. and S. Shelah, \"On the complexity of the Elzinga-Hearn algorithm for the 1-center problem,\" Math. Oper. Res. to appear.","key":"11_CR9","DOI":"10.1287\/moor.12.2.255"},{"key":"11_CR10","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1287\/trsc.6.4.379","volume":"6","author":"J. Elzinga","year":"1972","unstructured":"Elzinga, J. and D. W. Hearn, \"Geometric Solutions for some minimax location problems,\" Transportation Sci., 6, 1972, 379\u2013394.","journal-title":"Transportation Sci."},{"key":"11_CR11","volume-title":"Facility Layout and Location","author":"R.L. Francis","year":"1974","unstructured":"Francis, R.L. and J.A. White, Facility Layout and Location, Prentice-Hall, Englewood Cliffs, NJ, 1974."},{"doi-asserted-by":"crossref","unstructured":"Garey, M., R.L. Graham and D.S. Johnson, \"Some NP-complete problems,\" Proc. 8th ACM Annual Symp. on Theory of Comput., (May 1976) 10\u201322.","key":"11_CR12","DOI":"10.1145\/800113.803626"},{"unstructured":"Gonzales, T., \"Algorithms on sets and related problems,\" Tech. Rep. Dept. of Comput. Sci., Univ. of Oklahoma, 1975.","key":"11_CR13"},{"unstructured":"Hakimi, S. L., \"On locating new facilities in a competitive environment,\" ISOLDE II, June 1981, Skodsborg, Denmark.","key":"11_CR14"},{"doi-asserted-by":"crossref","unstructured":"Houle, M. E. and G. T. Toussaint, \"Computing the width of a set,\" Proc. 1st ACM Symp. of Computational Geometry, June 1985, 1\u20137.","key":"11_CR15","DOI":"10.1145\/323233.323234"},{"issue":"3","key":"11_CR16","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0196-6774(85)90005-7","volume":"6","author":"V. Klee","year":"1985","unstructured":"Klee, V. and M.C. Laskowski, \"Finding smallest triangles containing a given convex polygon,\" J. Algorithms, 6,3 (Sept. 1985), 359\u2013375.","journal-title":"J. Algorithms"},{"unstructured":"Lee, D.T., \"Farthest neighbor Voronoi diagrams and applications,\" Tech. Rep. No. 80-11-FC-04, Dept. EE\/CS, Northwestern Univ. 1980.","key":"11_CR17"},{"unstructured":"Lee, D.T., \"Maximum clique problem of rectangle graphs\", in Advances in Computing Research, Vol. 1, JAI Press, ed. F. P. Preparata, (1983) 91\u2013107.","key":"11_CR18"},{"issue":"12","key":"11_CR19","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1109\/TC.1984.1676388","volume":"C-33","author":"D. T. Lee","year":"1984","unstructured":"Lee, D. T. and F. P. Preparata, \"Computational geometry\u2014 A survey,\" IEEE Trans. Comput., C-33,12 (Dec 1984), 1072\u20131101.","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"11_CR20","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1137\/0209017","volume":"9","author":"D.T. Lee","year":"1980","unstructured":"Lee, D.T. and C.K. Wong, \"Voronoi diagrams in L1 \u2212 (L\u221e\u2212) metrics with 2-dimensional storage applications\", SIAM J. Comput., 9,1 (Feb. 1980) 200\u2013211.","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Lee, D.T. and Y.F. Wu, \"Geometric complexity of some location problems,\" Algorithmica, to appear.","key":"11_CR21","DOI":"10.1007\/BF01840442"},{"unstructured":"McKenna, M. and J. O'Rourke and S. Suri, \"Finding the largest rectangle in an orthogonal polygon,\" Allerton Conference on Comm. Control and Comput., (Oct. 1985) 486\u2013495","key":"11_CR22"},{"issue":"4","key":"11_CR23","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N., \"Linear time algorithm for linear programming in R3 and related problems\", SIAM J. Comput., 12,4 (Nov. 1983) 759\u2013776.","journal-title":"SIAM J. Comput."},{"unstructured":"Megiddo, N., \"Dynamic location problems,\" ISOLDE III, June 1984, Boston, MA.","key":"11_CR24"},{"issue":"1","key":"11_CR25","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N. and K.J. Supowit, \"On the complexity of some common geometric location problems,\" SIAM J. Comput., 13,1 (Feb. 1984) 182\u2013196.","journal-title":"SIAM J. Comput."},{"key":"11_CR26","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/0377-2217(83)90183-2","volume":"12","author":"J. G. Morris","year":"1983","unstructured":"Morris, J. G. and J. P. Norback, \"Linear facility location\u2014solving extensions of the basic problem,\" European J. Operational Res., 12, 1983, 90\u201394.","journal-title":"European J. Operational Res."},{"key":"11_CR27","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0166-218X(84)90124-0","volume":"8","author":"A. Naamad","year":"1984","unstructured":"Naamad, A., W.L. Hsu, and D.T. Lee, \"On maximum empty rectangle problem\", Discrete Appl. Math, 8 (1984), 267\u2013277.","journal-title":"Discrete Appl. Math"},{"doi-asserted-by":"crossref","unstructured":"O'Rourke, J., A. Aggarwal, S. Maddila and M. Baldwin, \"An optimal algorithm for finding minimal enclosing triangles,\" J. Algorithms, to appear.","key":"11_CR28","DOI":"10.1016\/0196-6774(86)90007-6"},{"key":"11_CR29","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C.H. Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H., \"The Euclidean traveling salesman problem is NP-complete,\" Theoret. Comput. Sci., 4 (1977) 237\u2013244.","journal-title":"Theoret. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Preparata, F.P. and M.I. Shamos, Computational Goemetry: An Introduction, Springer-Verlag, 1985.","key":"11_CR30","DOI":"10.1007\/978-1-4612-1098-6"},{"doi-asserted-by":"crossref","unstructured":"Shamos, M.I., \"Geometric complexity,\" Proc. 7th ACM Annual Symp. on Theory of Comput., (May 1975) 224\u2013233.","key":"11_CR31","DOI":"10.1145\/800116.803772"},{"doi-asserted-by":"crossref","unstructured":"Shamos, M.I. and D. Hoey, \"Closest-point problems,\" Proc. 16th IEEE Annual Symp. on Foundations of Comput. Sci., (Oct. 1975) 151\u2013162.","key":"11_CR32","DOI":"10.1109\/SFCS.1975.8"},{"unstructured":"Toussaint, G.T., \"Solving geometric problems with the rotating calipers,\" Proc. IEEE MELECON '83, Athens, Greece, May 1983.","key":"11_CR33"},{"issue":"5","key":"11_CR34","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/BF01008046","volume":"12","author":"G.T. Toussaint","year":"1983","unstructured":"Toussaint, G.T., \"Computing largest empty circle with location constraints,\" Int'l J. Computer and Info. Sci., 12,5 (Oct 1983) 347\u2013358.","journal-title":"Int'l J. Computer and Info. Sci."},{"unstructured":"Wu, Y.F. and D.T. Lee, \"Geometric competitive location problems,\" manuscript, 1986.","key":"11_CR35"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016240.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:35:33Z","timestamp":1607549733000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540167838"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/bfb0016240","relation":{},"subject":[]}}