{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:55Z","timestamp":1759639075042,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_6","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"65-77","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Batched Point Location in SINR Diagrams via Algebraic Tools"],"prefix":"10.1007","author":[{"given":"Boris","family":"Aronov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/978-3-540-73951-7_45","volume-title":"Algorithms and Data Structures","author":"D Ajwani","year":"2007","unstructured":"Ajwani, D., Ray, S., Seidel, R., Tiwary, H.R.: On computing the centroid of the vertices of an arrangement and related problems. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 519\u2013528. Springer, Heidelberg (2007)"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Andrews, M., Dinitz, M.: Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In: INFOCOM, pp. 1332\u20131340 (2009)","DOI":"10.1109\/INFCOM.2009.5062048"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Aronov, B., Katz, M.J.: Batched point location in SINR diagrams via algebraic tools (2014). arXiv:1412.0962 [cs.CG]","DOI":"10.1007\/978-3-662-47672-7_6"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Aurenhammer, F., Edelsbrunner, H.: An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition 251\u2013257 (1984)","DOI":"10.1016\/0031-3203(84)90064-5"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Avin, C., Cohen, A., Haddad, Y., Kantor, E., Lotker, Z., Parter, M., Peleg, D.: SINR diagram with interference cancellation. In: SODA, pp. 502\u2013515 (2012)","DOI":"10.1137\/1.9781611973099.43"},{"issue":"4","key":"6_CR6","doi-asserted-by":"publisher","first-page":"18:1","DOI":"10.1145\/2339123.2339125","volume":"59","author":"C Avin","year":"2012","unstructured":"Avin, C., Emek, Y., Kantor, E., Lotker, Z., Peleg, D., Roditty, L.: SINR diagrams: Convexity and its applications in wireless networks. J. ACM 59(4), 18:1\u2013318:4 (2012)","journal-title":"J. ACM"},{"key":"6_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0265-3","volume-title":"Polynomial and Matrix Computations: Fundamental Algorithms","author":"D Bini","year":"1994","unstructured":"Bini, D., Pan, V.Y.: Polynomial and Matrix Computations: Fundamental Algorithms, vol. 1. Birkhauser Verlag, Basel (1994)"},{"key":"6_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer-Verlag, Berlin (2008)","edition":"3"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Goussevskaia, O., Halld\u00f3rsson, M.M., Wattenhofer, R., Welzl, E.: Capacity of arbitrary wireless networks. In: INFOCOM, pp. 1872\u20131880 (2009)","DOI":"10.1109\/INFCOM.2009.5062108"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Goussevskaia, O., Oswald, Y.A., Wattenhofer, R.: Complexity in geometric SINR. In: MobiHoc, pp. 100\u2013109 (2007)","DOI":"10.1145\/1288107.1288122"},{"issue":"2","key":"6_CR11","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1109\/18.825799","volume":"46","author":"P Gupta","year":"2000","unstructured":"Gupta, P., Kumar, P.R.: The capacity of wireless networks. IEEE Trans. Information Theory 46(2), 388\u2013404 (2000)","journal-title":"IEEE Trans. Information Theory"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M.: Wireless scheduling with power control. ACM Transactions on Algorithms 9(1) (2012)","DOI":"10.1145\/2390176.2390183"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Mitra, P.: Wireless capacity with oblivious power in general metrics. In: SODA, pp. 1538\u20131548 (2011)","DOI":"10.1137\/1.9781611973082.119"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/978-3-642-02927-1_44","volume-title":"Automata, Languages and Programming","author":"MM Halld\u00f3rsson","year":"2009","unstructured":"Halld\u00f3rsson, M.M., Wattenhofer, R.: Wireless communication is in APX. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 525\u2013536. Springer, Heidelberg (2009)"},{"key":"6_CR15","unstructured":"Har-Peled, S., Kumar, N.: Approximating minimization diagrams and generalized proximity search. SIAM J. Comput. Accepted for publication. http:\/\/sarielhp.org\/p\/12\/wann\/wann.pdf"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Kumar, N.: Approximating minimization diagrams and generalized proximity search. In: FOCS, pp. 717\u2013726 (2013)","DOI":"10.1109\/FOCS.2013.82"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Kantor, E., Lotker, Z., Parter, M., Peleg, D.: The topology of wireless communication. In: STOC, pp. 383\u2013392 (2011)","DOI":"10.1145\/1993636.1993688"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Kesselheim, T.: A constant-factor approximation for wireless capacity maximization with power control in the SINR model. In: SODA, pp. 1549\u20131559 (2011)","DOI":"10.1137\/1.9781611973082.120"},{"issue":"2","key":"6_CR19","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/1814370.1814391","volume":"41","author":"Z Lotker","year":"2010","unstructured":"Lotker, Z., Peleg, D.: Structure and algorithms in the SINR wireless model. SIGACT News 41(2), 74\u201384 (2010)","journal-title":"SIGACT News"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Moroz, G., Aronov, B.: Computing the distance between piecewise-linear bivariate functions. In: SODA, pp. 288\u2013293 (2012)","DOI":"10.1137\/1.9781611973099.27"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Moroz, G., Aronov, B.: Computing the distance between piecewise-linear bivariate functions. ACM Transactions on Algorithms (2013). Accepted for publication arXiv:1107.2312 [cs.CG]","DOI":"10.1137\/1.9781611973099.27"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: The complexity of connectivity in wireless networks. In: INFOCOM, pp. 23\u201329 (2006)","DOI":"10.1109\/INFOCOM.2006.23"},{"key":"6_CR23","volume-title":"Modern Computer Algebra","author":"J von zur Gathen","year":"1999","unstructured":"von zur Gathen, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (1999)"},{"key":"6_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-03417-6_17","volume-title":"Wireless Algorithms, Systems, and Applications","author":"P-J Wan","year":"2009","unstructured":"Wan, P.-J., Jia, X., Yao, F.: Maximum independent set of links under physical interference model. In: Liu, B., Bestavros, A., Du, D.-Z., Wang, J. (eds.) WASA 2009. LNCS, vol. 5682, pp. 169\u2013178. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T15:24:22Z","timestamp":1674228262000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}