Output-sensitive algorithms for enumerating and counting simplices containing a given point in the plane

Amr Elmasry, Khaled Elbassioni

Research output: Contribution to conferencePaperpeer-review

5 Scopus citations

Abstract

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.

Original languageBritish English
Pages248-251
Number of pages4
StatePublished - 2005
Event17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada
Duration: 10 Aug 200512 Aug 2005

Conference

Conference17th Canadian Conference on Computational Geometry, CCCG 2005
Country/TerritoryCanada
CityWindsor
Period10/08/0512/08/05

Fingerprint

Dive into the research topics of 'Output-sensitive algorithms for enumerating and counting simplices containing a given point in the plane'. Together they form a unique fingerprint.

Cite this