On the arrangement of stochastic lines in R2

Yuan Li, Jie Xue, Akash Agrawal, Ravi Janardan

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1-20
Number of pages20
JournalJournal of Discrete Algorithms
StatePublished - May 2017

Bibliographical note

Publisher Copyright:
© 2017 Elsevier B.V.


  • Algorithms
  • Computational geometry
  • Data structures
  • Line arrangements
  • Stochastic problems
  • Voronoi Diagrams


Dive into the research topics of 'On the arrangement of stochastic lines in R<sup>2</sup>'. Together they form a unique fingerprint.

Cite this