Xavier Holt edited Points_Above_a_Line_Forming__.md  about 8 years ago

Commit id: 158a387dc26a41fde3d8a5030ab933845c3c08cc

deletions | additions      

       

## Querying  We form the arrangement \(A(S^*)\)  in \(O(n^2)\) time. We mark each cell faces \(\in A(S^*)\)  with the number of lines that lie above any point residing within \(\in S*\) lying strictly below  it (RTP: correctednes correctedness  and \(O(n^2)\) complexity. time.  This forms a planar-subdivision with \(O(n^2)\) edges. We Our query  then reduces to finding the face \(l^*\) resides in. To do this we  construct the trapezoidal-decomposition data-structure on \(A(S^*)\)  with preprocessing time \(O(n^2 log n)\), space \(O(n^2\log n)\) and query-time \(O(\) \(O(\log n)\) where we have made use of the fact that \(O(\log(n^2)) = O(\log n)\).  ## Face Annotation