Maximum Box Problem on Stochastic Points
Open Access
- 28 October 2021
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 83 (12) , 3741-3765
Abstract
Given a finite set of weighted points in $${\mathbb {R}}^d$$ (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 $$d=1$$ these computations are #P-hard, and give pseudo-polynomial time algorithms in the case where the weights are integers in a bounded interval. For $$d=2$$ , we consider that each point is colored red or blue, where red points have weight $$+1$$ and blue points weight $$-\infty $$ . 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.
Keywords
Funding Information
- H2020 Marie Skodowska-Curie Actions (734922)
- MINECO/FEDER (PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033)
This publication has 17 references indexed in Scilit:
- Maximum-weight planar boxes in time (and better)Information Processing Letters, 2014
- Closest pair and the post office problem for stochastic pointsComputational Geometry, 2014
- On the Most Likely Convex Hull of Uncertain Points2013
- The Union of Probabilistic Boxes: Maintaining the VolumeLecture Notes in Computer Science, 2011
- The Mono- and Bichromatic Empty Rectangle and Square Problems in All DimensionsLecture Notes in Computer Science, 2010
- Bichromatic separability with two boxes: A general approachJournal of Algorithms, 2009
- The complexity of power-index comparisonTheoretical Computer Science, 2009
- The Complexity of Counting in Sparse, Regular, and Planar GraphsSIAM Journal on Computing, 2001
- Allocating Bandwidth for Bursty ConnectionsSIAM Journal on Computing, 2000
- Monte-Carlo approximation algorithms for enumeration problemsJournal of Algorithms, 1989