{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:33:30Z","timestamp":1725536010079},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642033667"},{"type":"electronic","value":"9783642033674"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03367-4_1","type":"book-chapter","created":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T07:56:42Z","timestamp":1248076602000},"page":"1-12","source":"Crossref","is-referenced-by-count":2,"title":["On the Power of the Semi-Separated Pair Decomposition"],"prefix":"10.1007","author":[{"given":"Mohammad Ali","family":"Abam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paz","family":"Carmi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Farshi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM\u00a042, 67\u201390 (1995)","journal-title":"Journal of the ACM"},{"key":"1_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric spanner networks","author":"G. Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric spanner networks. Cambridge University Press, Cambridge (2007)"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.R.: A divide-and-conquer algorithm for min-cost perfect matching in the plane. In: FOCS 1998, pp. 320\u2013331 (1998)","DOI":"10.1109\/SFCS.1998.743466"},{"key":"1_CR4","unstructured":"Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. In: SODA 2007, pp. 1\u201310 (2007)"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J., Smid, M.: Geometric spanners for weighted point sets (manuscript) (2009)","DOI":"10.1007\/s00453-010-9465-2"},{"key":"1_CR6","first-page":"6037","volume":"258","author":"G. Hansel","year":"1964","unstructured":"Hansel, G.: Nombre minimal de contacts de fermeture n\u00e9cessaires pour r\u00e9aliser une fonction bool\u00e9enne sym\u00e9trique de n variables. C. R. Acad. Sci. Paris\u00a0258, 6037\u20136040 (1964); Russian transl., Kibern. Sb. (Nov. Ser.) 5, 47\u201352 (1968)","journal-title":"C. R. Acad. Sci. Paris"},{"issue":"4","key":"1_CR7","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1016\/j.ejc.2006.04.003","volume":"28","author":"B. Bollob\u00e1s","year":"2007","unstructured":"Bollob\u00e1s, B., Scott, A.: On separating systems. European Journal of Combinatorics\u00a028(4), 1068\u20131071 (2007)","journal-title":"European Journal of Combinatorics"},{"key":"1_CR8","unstructured":"Gupta, P., Janardan, R., Kumar, Y., Smid, M.: Data structures for range-aggregate extent queries. In: CCCG 2008, pp. 7\u201310 (2008)"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-540-78773-0_15","volume-title":"LATIN 2008: Theoretical Informatics","author":"P. Bose","year":"2008","unstructured":"Bose, P., Carmi, P., Courture, M., Maheshvari, A., Morin, P., Smid, M.: Spanners of complete k-partite geometric graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 170\u2013181. Springer, Heidelberg (2008)"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: STOC 1995, pp. 489\u2013498 (1995)","DOI":"10.1145\/225058.225191"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Arya, S., Mount, D.M., Smid, M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: FOCS 1994, pp. 703\u2013712 (1994)","DOI":"10.1109\/SFCS.1994.365722"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"L\u00f6ffler, M., Snoeyink, J.: Delaunay triangulations of imprecise points in linear time after preprocessing. In: SCG 2008, pp. 298\u2013304 (2008)","DOI":"10.1145\/1377676.1377727"},{"issue":"4","key":"1_CR13","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/j.jda.2008.04.002","volume":"6","author":"M. Kreveld van","year":"2008","unstructured":"van Kreveld, M., L\u00f6ffler, M.: Approximating largest convex hulls for imprecise points. Journal of Discrete Algorithms\u00a06(4), 583\u2013594 (2008)","journal-title":"Journal of Discrete Algorithms"},{"key":"1_CR14","unstructured":"Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: SODA 1993, pp. 291\u2013300 (1993)"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Advances in Discrete and Computational Geometry, pp. 1\u201356 (1999)","DOI":"10.1090\/conm\/223\/03131"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Nievergelt, J., Widmayer, P.: Spatial data structures: Concepts and design choices. In: Handbook of Computational Geometry, pp. 725\u2013764 (2000)","DOI":"10.1016\/B978-044482537-7\/50018-8"},{"issue":"12","key":"1_CR17","doi-asserted-by":"publisher","first-page":"1555","DOI":"10.1109\/TKDE.2004.93","volume":"16","author":"Y. Tao","year":"2004","unstructured":"Tao, Y., Papadias, D.: Range aggregate processing in spatial databases. IEEE Transactions on Knowledge and Data Engineering\u00a016(12), 1555\u20131570 (2004)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-540-45072-6_15","volume-title":"Advances in Spatial and Temporal Databases","author":"J. Shan","year":"2003","unstructured":"Shan, J., Zhang, D., Salzberg, B.: On spatial-range closest-pair query. In: Hadzilacos, T., Manolopoulos, Y., Roddick, J., Theodoridis, Y. (eds.) SSTD 2003. LNCS, vol.\u00a02750, pp. 252\u2013269. Springer, Heidelberg (2003)"},{"issue":"4","key":"1_CR19","first-page":"294","volume":"13","author":"P. Gupta","year":"2006","unstructured":"Gupta, P.: Range-aggregate query problems involving geometric aggregation operations. Nordic Journal of Computing\u00a013(4), 294\u2013308 (2006)","journal-title":"Nordic Journal of Computing"},{"key":"1_CR20","unstructured":"Sharathkumar, R., Gupta, P.: Range-aggregate proximity queries. Technical Report IIIT\/TR\/2007\/80, IIIT Hyderabad (2007)"},{"key":"1_CR21","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, 3rd edn. Springer, Heidelberg (2008)","edition":"3"},{"issue":"2","key":"1_CR22","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0925-7721(99)00014-0","volume":"13","author":"S. Arya","year":"1999","unstructured":"Arya, S., Mount, D.M., Smid, M.: Dynamic algorithms for geometric spanners of small diameter: Randomized solutions. Computational Geometry: Theory and Applications\u00a013(2), 91\u2013107 (1999)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.comgeo.2004.01.003","volume":"28","author":"P. Bose","year":"2004","unstructured":"Bose, P., Gudmundsson, J., Morin, P.: Ordered theta graphs. Computational Geometry: Theory and Applications\u00a028, 11\u201318 (2004)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1006\/jagm.2000.1135","volume":"38","author":"C.A. Duncan","year":"2001","unstructured":"Duncan, C.A., Goodrich, M.T., Kobourov, S.: Balanced aspect ratio trees: Combining the advances of k-d trees and octrees. J. of Algorithms\u00a038, 303\u2013333 (2001)","journal-title":"J. of Algorithms"}],"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-03367-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T15:28:55Z","timestamp":1558452535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03367-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033667","9783642033674"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03367-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}