{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:43Z","timestamp":1740109303940,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Skodowska-Curie Actions","doi-asserted-by":"publisher","award":["734922"],"award-info":[{"award-number":["734922"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"MINECO\/FEDER","award":["PID2019-104129GB-I00\/ MCIN\/ AEI\/ 10.13039\/501100011033"],"award-info":[{"award-number":["PID2019-104129GB-I00\/ MCIN\/ AEI\/ 10.13039\/501100011033"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a finite set of weighted points in <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {R}}^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>R<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (where there can be negative weights), the maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized. We consider that each point of the input has a probability of being present in the final random point set, and these events are mutually independent; then, the total weight of a maximum box is a random variable. We aim to compute both the probability that this variable is at least a given parameter, and its expectation. We show that even in <jats:inline-formula><jats:alternatives><jats:tex-math>$$d=1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> these computations are #P-hard, and give pseudo-polynomial time algorithms in the case where the weights are integers in a bounded interval. For <jats:inline-formula><jats:alternatives><jats:tex-math>$$d=2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we consider that each point is colored red or blue, where red points have weight <jats:inline-formula><jats:alternatives><jats:tex-math>$$+1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and blue points weight <jats:inline-formula><jats:alternatives><jats:tex-math>$$-\\infty $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>\u221e<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The random variable is the maximum number of red points that can be covered with a box not containing any blue point. We prove that the above two computations are also #P-hard, and give a polynomial-time algorithm for computing the probability that there is a box containing exactly two red points, no blue point, and a given point of the plane.<\/jats:p>","DOI":"10.1007\/s00453-021-00882-z","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T08:02:52Z","timestamp":1635408172000},"page":"3741-3765","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximum Box Problem on Stochastic Points"],"prefix":"10.1007","volume":"83","author":[{"given":"Luis E.","family":"Caraballo","sequence":"first","affiliation":[]},{"given":"Pablo","family":"P\u00e9rez-Lantero","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0095-1725","authenticated-orcid":false,"given":"Carlos","family":"Seara","sequence":"additional","affiliation":[]},{"given":"Inmaculada","family":"Ventura","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"issue":"1","key":"882_CR1","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1023\/A:1009942427413","volume":"6","author":"P Alliez","year":"2000","unstructured":"Alliez, P., Devillers, O., Snoeyink, J.: Removing degeneracies by perturbing the problem or perturbing the world. Reliable Comput. 6(1), 61\u201379 (2000)","journal-title":"Reliable Comput."},{"doi-asserted-by":"crossref","unstructured":"Backer, J., Keil, J.M.: The mono- and bichromatic empty rectangle and square problems in all dimensions. In: LATIN\u201910, pp. 14\u201325 (2010)","key":"882_CR2","DOI":"10.1007\/978-3-642-12200-2_3"},{"issue":"8","key":"882_CR3","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.ipl.2014.03.007","volume":"114","author":"J Barbay","year":"2014","unstructured":"Barbay, J., Chan, T.M., Navarro, G., P\u00e9rez-Lantero, P.: Maximum-weight planar boxes in $${O}(n^2)$$ time (and better). Inf. Process. Lett. 114(8), 437\u2013445 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"882_CR4","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s10878-015-9971-x","volume":"33","author":"LE Caraballo","year":"2017","unstructured":"Caraballo, L.E., Ochoa, C., P\u00e9rez-Lantero, P., Rojas-Ledesma, J.: Matching colored points with rectangles. J. Comb. Optim. 33(2), 403\u2013421 (2017)","journal-title":"J. Comb. Optim."},{"doi-asserted-by":"crossref","unstructured":"Chan, T.M., Kamousi, P., Suri, S.: Stochastic minimum spanning trees in Euclidean spaces. In: SoCG\u201911, pp. 65\u201374 (2011)","key":"882_CR5","DOI":"10.1145\/1998196.1998206"},{"issue":"2\u20133","key":"882_CR6","doi-asserted-by":"publisher","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"},{"unstructured":"Czyzowicz, J., Kranakis, E., Urrutia, J.: Guarding the convex subsets of a point-set. In: 12th Canadian Conference on Computational Geometry, pp. 47\u201350. Fredericton, New Brunswick (2000)","key":"882_CR7"},{"issue":"1","key":"882_CR8","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.tcs.2008.09.034","volume":"410","author":"P Faliszewski","year":"2009","unstructured":"Faliszewski, P., Hemaspaandra, L.: The complexity of power-index comparison. Theoret. Comput. Sci. 410(1), 101\u2013107 (2009)","journal-title":"Theoret. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Feldman, D., Munteanu, A., Sohler, C.: Smallest enclosing ball for probabilistic data. In: SoCG\u201914, pp. 214\u2013223 (2014)","key":"882_CR9","DOI":"10.1145\/2582112.2582114"},{"issue":"2","key":"882_CR10","first-page":"32","volume":"8","author":"M Fink","year":"2017","unstructured":"Fink, M., Hershberger, J., Kumar, N., Suri, S.: Hyperplane separability and convexity of probabilistic point sets. J. Comput. Geom. 8(2), 32\u201357 (2017)","journal-title":"J. Comput. Geom."},{"issue":"2","key":"882_CR11","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.comgeo.2012.10.010","volume":"47","author":"P Kamousi","year":"2014","unstructured":"Kamousi, P., Chan, T.M., Suri, S.: Closest pair and the post office problem for stochastic points. Comput. Geom. 47(2), 214\u2013223 (2014)","journal-title":"Comput. Geom."},{"issue":"3","key":"882_CR12","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"RM Karp","year":"1989","unstructured":"Karp, R.M., Luby, M., Madras, N.: Monte-Carlo approximation algorithms for enumeration problems. J. Algorithms 10(3), 429\u2013448 (1989)","journal-title":"J. Algorithms"},{"issue":"1","key":"882_CR13","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/S0097539797329142","volume":"30","author":"J Kleinberg","year":"2000","unstructured":"Kleinberg, J., Rabani, Y., Tardos, \u00c9.: Allocating bandwidth for bursty connections. SIAM J. Comput. 30(1), 191\u2013217 (2000)","journal-title":"SIAM J. Comput."},{"key":"882_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"issue":"8","key":"882_CR15","doi-asserted-by":"publisher","first-page":"1144","DOI":"10.1093\/comjnl\/bxv124","volume":"59","author":"P P\u00e9rez-Lantero","year":"2016","unstructured":"P\u00e9rez-Lantero, P.: Area and perimeter of the convex hull of stochastic points. Comput. J. 59(8), 1144\u20131154 (2016)","journal-title":"Comput. J."},{"doi-asserted-by":"crossref","unstructured":"Suri, S., Verbeek, K., Y\u0131ld\u0131z, H.: On the most likely convex hull of uncertain points. In: ESA\u201913, pp. 791\u2013802 (2013)","key":"882_CR16","DOI":"10.1007\/978-3-642-40450-4_67"},{"issue":"2","key":"882_CR17","first-page":"24:1","volume":"23","author":"C Tsirogiannis","year":"2018","unstructured":"Tsirogiannis, C., Staals, F., Pellissier, V.: Computing the expected value and variance of geometric measures. J. Exp. Algorithmics 23(2), 24:1-24:32 (2018)","journal-title":"J. Exp. Algorithmics"},{"issue":"2","key":"882_CR18","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"SP Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31(2), 398\u2013427 (2001)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"882_CR19","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"100","author":"LG Valiant","year":"1981","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. 100(2), 135\u2013140 (1981)","journal-title":"IEEE Trans. Comput."},{"doi-asserted-by":"crossref","unstructured":"Y\u0131ld\u0131z, H., Foschini, L., Hershberger, J., Suri, S.: The union of probabilistic boxes: maintaining the volume. In: ESA, pp. 591\u2013602 (2011)","key":"882_CR20","DOI":"10.1007\/978-3-642-23719-5_50"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00882-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00882-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00882-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T11:39:22Z","timestamp":1637321962000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00882-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":20,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["882"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00882-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"24 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}