We study data structures to answer window queries using stochastic input sequences. The first problem is the most likely maximal point in a query window: Let α1,αc be constants, with 0 < α1 < α2 < < αc < 1. Let P = P1 P2 Pc be a set of n points in d, for some fixed d. For i = 1, 2,c, each point in Pi is associated with a probability αi of existence. A point p = (x1,xd) in P is on the maximal layer of P if there is no other point q = (x1′,x d′) in P such that x1′ x 1,x2′ x 2, and xd′ x d. Consider a random subset of P obtained by including, for i = 1, 2,c, each point of Pi independently with probability αi. For a query interval [i,j], with i ≤ j, we report the point in Pi,j = (pi,pj) that has the highest probability to be on the maximal layer of Pi,j in O(1) time using O(nlog n) space. We solve a special problem as follows. A sequence P of n points in d is given (d ≥ 2), where each point P has a probability (0, 1] of existence associated with it. Given a query interval [i,j] and an integer t with i ≤ t ≤ j, we report the probability of pt to be on the maximal layer of Pi,j in O(logdn) time using O(nlogdn) space. The second problem we consider is the most likely common element problem. Let = {1, 2,n} be the universe. Let S1,S1,Sm be a sequence of random subsets of such that for p = 1,m and i = 1,n, element i is added to Sp with probability αpi (independently of other choices). Let τ be a fixed real number with 0 < τ ≤ 1. For query indices p, q, i and j, with 1 ≤ p ≤ q ≤ m and 1 ≤ i ≤ j ≤ n, we decide whether there exists an element k with i ≤ k ≤ j such that Pr(k nr=pqS r) ≥ τ in O(1) time using O(mn) space and report these elements in O(log n + w) time, where w is the size of the output.

Maximal point, most likely common element, set membership, window query
dx.doi.org/10.1142/S0218195919500092
International Journal of Computational Geometry and Applications
Computational Geometry Lab

Carmi, P. (Paz), Chanchary, F. (Farah), Maheshwari, A, & Smid, M. (2019). The Most Likely Object to be Seen Through a Window. International Journal of Computational Geometry and Applications, 29(4), 269–287. doi:10.1142/S0218195919500092