On the arrangement of stochastic lines in R2

Consider a set of n stochastic lines in R2, where the existence probability of each line is determined by a fixed probability distribution. For a fixed x-coordinate q, the n lines from top to bottom can be represented by an ordered n-element sequence. Consider all the (nk)k-element sub-sequences of that n-element sequence. Each k-element sub-sequence has an associated likelihood to be the true k-topmost lines at x-coordinate q, and the one with the largest probability is defined as the most likely k-topmost lines at q. This paper studies the most likely k-topmost lines of the arrangement of n lines taken over all the x-coordinates. Let cnt be the total number of distinct sequences of the most likely k-topmost lines over all x-coordinates. The main result established is that the expected value of cnt is O(kn), which implies that it is possible to store all the distinct most likely k-topmost lines in O(k2n) expected space. An example is given showing that cnt, in the worst case, can be Θ(n2) even when k=1. This highlights the value of the expected bound. An algorithm is also given to compute the most likely k-topmost lines of the arrangement. Applications of this result to the stochastic Voronoi Diagram in R1 and to the stochastic preference top-k query in R2 are discussed.