On the arrangement of stochastic lines in R2

Abstract Consider a set of n stochastic lines in R 2 , 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 ( n k ) 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 ( k n ) , which implies that it is possible to store all the distinct most likely k -topmost lines in O ( k 2 n ) expected space. An example is given showing that cnt , in the worst case, can be Θ ( n 2 ) 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 R 1 and to the stochastic preference top- k query in R 2 are discussed.