{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:31:46Z","timestamp":1725550306700},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540304678"},{"type":"electronic","value":"9783540320890"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11589440_7","type":"book-chapter","created":{"date-parts":[[2005,11,9]],"date-time":"2005-11-09T12:08:15Z","timestamp":1131538095000},"page":"62-75","source":"Crossref","is-referenced-by-count":1,"title":["Farthest-Point Queries with Geometric and Combinatorial Constraints"],"prefix":"10.1007","author":[{"given":"Ovidiu","family":"Daescu","sequence":"first","affiliation":[]},{"given":"Ningfang","family":"Mi","sequence":"additional","affiliation":[]},{"given":"Chan-Su","family":"Shin","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"7_CR1","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0925-7721(92)90001-9","volume":"1","author":"P.K. Agarwal","year":"1992","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Suri, S.: Farthest neighbors, maximum spanning trees and related problems in higher dimensions. Computational Geometry: Theory and Applications\u00a01(4), 189\u2013201 (1992)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"6","key":"7_CR2","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1989","unstructured":"Aggarwal, A., Guibas, L.J., Saxe, J.B., Shor, P.W.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete & Computational Geometry\u00a04(6), 591\u2013604 (1989)","journal-title":"Discrete & Computational Geometry"},{"issue":"1","key":"7_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0020-0190(89)90103-8","volume":"31","author":"A. Aggarwal","year":"1989","unstructured":"Aggarwal, A., Kravets, D.: A linear time algorithm for finding all farthest neighbors in a convex polygon. Information Processing letters\u00a031(1), 17\u201320 (1989)","journal-title":"Information Processing letters"},{"issue":"5","key":"7_CR4","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1142\/S0218195903001268","volume":"13","author":"S. Bespamyatnikh","year":"2003","unstructured":"Bespamyatnikh, S.: Computing closest points for segments. Int. J. Comput. Geom. Appl.\u00a013(5), 419\u2013438 (2003)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"7_CR5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0925-7721(99)00055-3","volume":"16","author":"S. Bespamyatnikh","year":"2000","unstructured":"Bespamyatnikh, S., Snoeyink, J.: Queries with segments in Voronoi diagrams. Comput. Geom. Theory Appl.\u00a016(1), 23\u201333 (2000)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"7_CR6","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S0218195903001086","volume":"13","author":"D.Z. Chen","year":"2003","unstructured":"Chen, D.Z., Daescu, O.: Space-efficient algorithms for approximating polygonal curves in two dimensional space. International Journal of Computational Geometry and Applications\u00a013(2), 95\u2013112 (2003)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"7_CR7","unstructured":"Chen, D.Z., Daescu, O., Hershberger, J., Kogge, P.M., Snoeyink, J.: Polygonal path approximation with angle constraints. In: Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA 2001), pp. 342\u2013343 (2001)"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(02)00431-0","volume":"296","author":"O. Cheong","year":"2003","unstructured":"Cheong, O., Shin, C.-S., Vigneron, A.: Computing farthest neighbors on a convex polytope. Theoretical Computer Science\u00a0296, 47\u201358 (2003)","journal-title":"Theoretical Computer Science"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Cole, R., Yap, C.-K.: Geometric retrieval problems. In: Proc. 24th Ann. IEEE Symposium on Foundations of Computer Science (FOCS 1983), pp. 112\u2013121 (1983)","DOI":"10.1109\/SFCS.1983.22"},{"key":"7_CR10","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (1990)"},{"issue":"1","key":"7_CR11","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.comgeo.2004.07.001","volume":"30","author":"O. Daescu","year":"2005","unstructured":"Daescu, O., Mi, N.: Polygonal path approximation: A query based approach. Computational Geometry: Theory and Applications\u00a030(1), 41\u201358 (2005)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM Journal on Computing\u00a015, 317\u2013340 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/3-540-45753-4_14","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"J. Gudmundsson","year":"2002","unstructured":"Gudmundsson, J., Haverkort, H., Park, S.-M., Shin, C.-S., Wolff, A.: Facility location and the geometric minimum-diameter spanning tree. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 146\u2013160. Springer, Heidelberg (2002)"},{"issue":"1","key":"7_CR14","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.comgeo.2003.07.007","volume":"27","author":"J. Gudmundsson","year":"2004","unstructured":"Gudmundsson, J., Haverkort, H., Park, S.-M., Shin, C.-S., Wolff, A.: Facility location and the geometric minimum-diameter spanning tree. Computational Geometry: Theory and Applications\u00a027(1), 87\u2013106 (2004)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"7_CR15","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: Sorting and Searching. In: The Art of Computer Programming, vol.\u00a03, Addison-Wesley, Reading (1973)"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Efficient partition trees. Discrete and Computational Geometry\u00a08, 315\u2013334 (1992)","journal-title":"Discrete and Computational Geometry"},{"issue":"3","key":"7_CR17","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/500559.500562","volume":"32","author":"J.S.B. Mitchell","year":"2001","unstructured":"Mitchell, J.S.B., O\u2019Rourke, J.: Computational geometry column 42. SIGACT News\u00a032(3), 63\u201372 (2001)","journal-title":"SIGACT News"},{"issue":"11","key":"7_CR18","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1016\/S0167-8655(98)00080-4","volume":"19","author":"P. Mitra","year":"1998","unstructured":"Mitra, P., Chaudhuri, B.: Efficiently computing the closest point to a query line. Pattern Recognition Letters\u00a019(11), 1027\u20131035 (1998)","journal-title":"Pattern Recognition Letters"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Mukhopadhyay, A.: Using simplicial partitions to determine a closest point to a query line. In: Proc. Canadian Conf. Comp. Geom (CCCG 2002), pp. 10\u201312 (2002)","DOI":"10.1016\/S0167-8655(03)00018-7"},{"key":"7_CR20","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1990","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Heidelberg (1990)"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"P.M. Vaidya","year":"1989","unstructured":"Vaidya, P.M.: An O(n logn) algorithm for the all-nearest-neighbors problem. Discrete and Computational Geometry\u00a04, 101\u2013115 (1989)","journal-title":"Discrete and Computational Geometry"}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11589440_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:01:36Z","timestamp":1605643296000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11589440_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540304678","9783540320890"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11589440_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}