Similar to point location

2018-10-13 19:48:38

I have a following problem:

Given a set $S$ consisting $N$ triangles (possibly overlapping). Answer queries (online) of the form: given a point $P$ is there a triangle $T$ in $S$, such that $P$ lies inside $T$?

I am interested in solution (data structure) which:

$*$ Answer query faster than $O(N)$ (worst case)

$*$ Preprocesses triangles faster that $O(N^2)$ (worst case)

Problem looks classic, but I am new to computational geometry.