Output-Sensitive Algorithms for Enumerating and Counting Simplices Containing a Given Point in th Plane
Amr Elmasry, Khaled Elbassioni · MPG.PuRe (Max Planck Society) · 2005
Given a set of n points S ⊆ R2, a specified point Z ∈ R2, it is shown that finding k minimal simplices from S, each of which contains Z, can be done in O(n+k) time. It is also shown that counting the number of all such simplices can be done in O(n + n log (k/n+ 1)) time, when the number of simplices is k.