{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T11:07:26Z","timestamp":1763809646633},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319530062"},{"type":"electronic","value":"9783319530079"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-53007-9_2","type":"book-chapter","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T05:13:23Z","timestamp":1486012403000},"page":"12-23","source":"Crossref","is-referenced-by-count":1,"title":["Polynomial Time Algorithms for Bichromatic Problems"],"prefix":"10.1007","author":[{"given":"Sayan","family":"Bandyapadhyay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aritra","family":"Banik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,26]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Suri, S.: Fast algorithms for computing the largest empty rectangle. In: SoCG, Waterloo, Canada, pp. 278\u2013290 (1987)","key":"2_CR1","DOI":"10.1145\/41958.41988"},{"unstructured":"Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B., Simakov, M.: Conflict-free covering. In: CCCG, Kingston, Ontario, Canada, 10\u201312 August 2015","key":"2_CR2"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-662-48971-0_28","volume-title":"Algorithms and Computation","author":"EM Arkin","year":"2015","unstructured":"Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B., Simakov, M.: Choice is hard. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 318\u2013328. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48971-0_28"},{"issue":"2","key":"2_CR4","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.comgeo.2014.08.004","volume":"48","author":"EM Arkin","year":"2015","unstructured":"Arkin, E.M., D\u00edaz-B\u00e1\u00f1ez, J.M., Hurtado, F., Kumar, P., Mitchell, J.S.B., Palop, B., P\u00e9rez-Lantero, P., Saumell, M., Silveira, R.I.: Bichromatic 2-center of pairs of points. Comput. Geom. 48(2), 94\u2013107 (2015)","journal-title":"Comput. Geom."},{"unstructured":"Armaselu, B., Daescu, O.: Maximum area rectangle separating red and blue points. In: CCCG 2016, British Columbia, Canada, 3\u20135 August 2016, pp. 244\u2013251 (2016)","key":"2_CR5"},{"issue":"3","key":"2_CR6","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1137\/060669474","volume":"38","author":"B Aronov","year":"2008","unstructured":"Aronov, B., Har-Peled, S.: On approximating the depth and related problems. SIAM J. Comput. 38(3), 899\u2013921 (2008)","journal-title":"SIAM J. Comput."},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-642-12200-2_3","volume-title":"LATIN 2010: Theoretical Informatics","author":"J Backer","year":"2010","unstructured":"Backer, J., Keil, J.M.: The mono- and bichromatic empty rectangle and square problems in all dimensions. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 14\u201325. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-12200-2_3"},{"unstructured":"Backer, J., Mark Keil, J.: The bichromatic square and rectangle problems. Technical report 2009\u201301, University of Saskatchewan (2009)","key":"2_CR8"},{"issue":"4","key":"2_CR9","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1145\/1383369.1383375","volume":"4","author":"A Bar-Noy","year":"2008","unstructured":"Bar-Noy, A., Cheilaris, P., Smorodinsky, S.: Deterministic conflict-free coloring for intervals: from offline to online. ACM Trans. Algorithms 4(4), 44 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"2_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-319-44543-4_6","volume-title":"Combinatorial Algorithms","author":"A Biniaz","year":"2016","unstructured":"Biniaz, A., Bose, P., Maheshwari, A., Smid, M.: Plane bichromatic trees of low degree. In: M\u00e4kinen, V., Puglisi, S.J., Salmela, L. (eds.) IWOCA 2016. LNCS, vol. 9843, pp. 68\u201380. Springer, Heidelberg (2016). doi: 10.1007\/978-3-319-44543-4_6"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-319-21840-3_6","volume-title":"Algorithms and Data Structures","author":"A Biniaz","year":"2015","unstructured":"Biniaz, A., Maheshwari, A., Nandy, S.C., Smid, M.: An optimal algorithm for plane matchings in multipartite geometric graphs. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 66\u201378. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-21840-3_6"},{"doi-asserted-by":"crossref","unstructured":"Bitner, S., Cheung, Y.K., Daescu, O.: Minimum separating circle for bichromatic points in the plane. In: ISVD 2010, Quebec, Canada, June 28\u201330, 2010, pp. 50\u201355 (2010)","key":"2_CR12","DOI":"10.1109\/ISVD.2010.14"},{"doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Output-sensitive results on convex hulls, extreme points, and related problems. In: SOCG, Vancouver, B.C., Canada, 5\u201312 June 1995, pp. 10\u201319 (1995)","key":"2_CR13","DOI":"10.1145\/220279.220281"},{"issue":"1","key":"2_CR14","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0196-6774(02)00285-7","volume":"46","author":"J Chaudhuri","year":"2003","unstructured":"Chaudhuri, J., Nandy, S.C., Das, S.: Largest empty rectangle among a point set. J. Algorithms 46(1), 54\u201378 (2003)","journal-title":"J. Algorithms"},{"issue":"1","key":"2_CR15","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0215022","volume":"15","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B., (Scot) Drysdale III, R.L., Lee, D.T.: Computing the largest empty rectangle. SIAM J. Comput. 15(1), 300\u2013315 (1986)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2_CR16","doi-asserted-by":"crossref","first-page":"732","DOI":"10.1007\/s00453-014-9929-x","volume":"70","author":"P Cheilaris","year":"2014","unstructured":"Cheilaris, P., Gargano, L., Rescigno, A.A., Smorodinsky, S.: Strong conflict-free coloring for intervals. Algorithmica 70(4), 732\u2013749 (2014)","journal-title":"Algorithmica"},{"issue":"5","key":"2_CR17","doi-asserted-by":"crossref","first-page":"1342","DOI":"10.1137\/S0097539704446682","volume":"36","author":"K Chen","year":"2007","unstructured":"Chen, K., Fiat, A., Kaplan, H., Levy, M., Matousek, J., Mossel, E., Pach, J., Sharir, M., Smorodinsky, S., Wagner, U., Welzl, E.: Online conflict-free coloring for intervals. SIAM J. Comput. 36(5), 1342\u20131359 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"2_CR18","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jalgor.2009.01.001","volume":"64","author":"C Cort\u00e9s","year":"2009","unstructured":"Cort\u00e9s, C., D\u00edaz-B\u00e1\u00f1ez, J.M., P\u00e9rez-Lantero, P., Seara, C., Urrutia, J., Ventura, I.: Bichromatic separability with two boxes: a general approach. J. Algorithms 64(2\u20133), 79\u201388 (2009)","journal-title":"J. Algorithms"},{"key":"2_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801389","volume-title":"An Introduction to Support Vector Machines: And Other Kernel-based Learning Methods","author":"N Cristianini","year":"2000","unstructured":"Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines: And Other Kernel-based Learning Methods. Cambridge University Press, New York (2000)"},{"doi-asserted-by":"crossref","unstructured":"Dey, T.K.: Improved bounds on planar k-sets and k-levels. In: FOCS, Miami Beach, Florida, USA, 19\u201322 October 1997, pp. 156\u2013161 (1997)","key":"2_CR20","DOI":"10.1109\/SFCS.1997.646104"},{"key":"2_CR21","volume-title":"Pattern Classification","author":"RO Duda","year":"2000","unstructured":"Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification. Wiley, New York (2000)"},{"issue":"3","key":"2_CR22","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1023\/A:1020546910706","volume":"23","author":"J Eckstein","year":"2002","unstructured":"Eckstein, J., Hammer, P.L., Liu, Y., Nediak, M., Simeone, B.: The maximum box problem and its application to data analysis. Comp. Opt. Appl. 23(3), 285\u2013298 (2002)","journal-title":"Comp. Opt. Appl."},{"issue":"1","key":"2_CR23","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1137\/S0097539702431840","volume":"33","author":"G Even","year":"2003","unstructured":"Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33(1), 94\u2013136 (2003)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2_CR24","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.comgeo.2004.02.001","volume":"29","author":"PP Goswami","year":"2004","unstructured":"Goswami, P.P., Das, S., Nandy, S.C.: Triangular range counting query in 2d and its application in finding k nearest neighbors of a line segment. Comput. Geom. 29(3), 163\u2013175 (2004)","journal-title":"Comput. Geom."},{"key":"2_CR25","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/978-3-642-55566-4_25","volume-title":"Discrete and Computational Geometry, Algorithms and Combinatorics","author":"A Kaneko","year":"2003","unstructured":"Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane a survey. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry, Algorithms and Combinatorics, vol. 25, pp. 551\u2013570. Springer, Heidelberg (2003)"},{"issue":"9","key":"2_CR26","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1016\/j.comgeo.2012.01.013","volume":"45","author":"MJ Katz","year":"2012","unstructured":"Katz, M.J., Lev-Tov, N., Morgenstern, G.: Conflict-free coloring of points on a line with respect to a set of intervals. Comput. Geom. 45(9), 508\u2013514 (2012)","journal-title":"Comput. Geom."},{"unstructured":"Liu, Y., Nediak, M.: Planar case of the maximum box and related problems. In: CCCG 2003, Halifax, Canada, 11\u201313 August 2003, pp. 14\u201318 (2003)","key":"2_CR27"},{"issue":"3","key":"2_CR28","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., Lee, D.T., Hsu, W.-L.: On the maximum empty rectangle problem. Discret. Appl. Math. 8(3), 267\u2013277 (1984)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"2_CR29","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01840377","volume":"5","author":"M Orlowski","year":"1990","unstructured":"Orlowski, M.: A new algorithm for the largest empty rectangle problem. Algorithmica 5(1), 65\u201373 (1990)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53007-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T05:35:19Z","timestamp":1498368919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53007-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319530062","9783319530079"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53007-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}