Data Structures for Restricted Triangular Range Searching
Mashhood Ishaque, Diane L. Souvaine, Nadia M. Benbernou · Canadian Conference on Computational Geometry · 2008
We present data structures for triangular emptiness and reporting queries for a planar point set, where the query triangle contains the origin. The data structures use near-linear space and achieve polylogarithmic query times.