{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:23:33Z","timestamp":1760441013252},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642222993"},{"type":"electronic","value":"9783642223006"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22300-6_46","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T08:41:31Z","timestamp":1312879291000},"page":"548-559","source":"Crossref","is-referenced-by-count":9,"title":["Closest Pair and the Post Office Problem for Stochastic Points"],"prefix":"10.1007","author":[{"given":"Pegah","family":"Kamousi","sequence":"first","affiliation":[]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"46_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Agarwal, P.K., Arge, L., Larsen, K.G., Phillips, J.M.: (Approximate) uncertain skylines. In: ICDT, pp. 186\u2013196 (2011)","DOI":"10.1145\/1938551.1938576"},{"key":"46_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Cheng, S.-W., Tao, Y., Yi, K.: Indexing uncertain data. In: PODS, pp. 137\u2013146 (2009)","DOI":"10.1145\/1559795.1559816"},{"key":"46_CR3","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM\u00a045, 891\u2013923 (1998)","journal-title":"J. ACM"},{"key":"46_CR4","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/PL00009390","volume":"20","author":"T.M. Chan","year":"1998","unstructured":"Chan, T.M.: Approximate Nearest Neighbor Queries Revisited. Discrete and Computational Geometry\u00a020, 359\u2013373 (1998)","journal-title":"Discrete and Computational Geometry"},{"key":"46_CR5","unstructured":"Chan, T.M.: Closest-point problems simplified on the RAM. In: Proc. SODA, pp. 472\u2013473 (2002)"},{"key":"46_CR6","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms\u00a046, 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"key":"46_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational geometry: algorithms and applications","author":"M. Berg De","year":"2008","unstructured":"De Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational geometry: algorithms and applications. Springer, Heidelberg (2008)"},{"issue":"4","key":"46_CR8","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The Rectilinear Steiner Tree Problem is NP-Complete. SIAM Journal on Applied Mathematics\u00a032(4), 826\u2013834 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"46_CR9","volume-title":"Inequalities","author":"G.H. Hardy","year":"1952","unstructured":"Hardy, G.H., Polya, G., Littlewood, J.E.: Inequalities. Cambridge Press, New York (1952)"},{"key":"46_CR10","doi-asserted-by":"crossref","unstructured":"Kamousi, P., Chan, T., Suri, S.: Stochastic Minimum Spanning Trees in Euclidean Spaces. In: Proc. SoCG (2011) (to appear)","DOI":"10.1145\/1998196.1998206"},{"key":"46_CR11","unstructured":"Klain, D.A., Rota, G.: Introduction to Geometric Probability, Cambridge (1997)"},{"key":"46_CR12","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, Reading (1973)"},{"key":"46_CR13","doi-asserted-by":"publisher","first-page":"1187","DOI":"10.1016\/j.ipl.2009.08.003","volume":"109","author":"M.-S. Lin","year":"2009","unstructured":"Lin, M.-S., Chen, Y.-J.: Counting the number of vertex covers in a trapezoid graph. Inf. Process. Lett.\u00a0109, 1187\u20131192 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"46_CR14","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00453-008-9174-2","volume":"56","author":"M. L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., van Kreveld, M.J.: Largest and Smallest Convex Hulls for Imprecise Points. Algorithmica\u00a056(2), 235\u2013269 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"46_CR15","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"J.S. Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput.\u00a012(4), 777\u2013788 (1983)","journal-title":"SIAM J. Comput."},{"key":"46_CR16","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S.P. Vadhan","year":"1997","unstructured":"Vadhan, S.P.: The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM Journal on Computing\u00a031, 398\u2013427 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"46_CR17","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"L. Valiant","year":"1981","unstructured":"Valiant, L.: Universality Considerations in VLSI Circuits. IEEE Trans. Computers\u00a030, 135\u2013140 (1981)","journal-title":"IEEE Trans. Computers"},{"issue":"3","key":"46_CR18","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM Journal on Computing"},{"issue":"7","key":"46_CR19","doi-asserted-by":"publisher","first-page":"2990","DOI":"10.1137\/090753620","volume":"39","author":"M.J. Kreveld van","year":"2010","unstructured":"van Kreveld, M.J., L\u00f6ffler, M., Mitchell, J.S.B.: Preprocessing Imprecise Points and Splitting Triangulations. SIAM J. Comput.\u00a039(7), 2990\u20133000 (2010)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22300-6_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T18:54:07Z","timestamp":1560452047000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22300-6_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642222993","9783642223006"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22300-6_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}