Repeated point in polygon: preprocessing complexity given logarithmic query time?

Question

I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is not necessarily simple. I am interested in the case where a polygon has many edges.

Let $n$ be the number of vertices of the polygon. I have an algorithm that performs the online phase in $O(\log n)$ time but the preprocessing phase requires $O(n^3)$ time and space in general, $O(n^2)$ time and space for simple polygons, and $O(n)$ time for star-shaped polygons.

Can we do better? Specifically, does anyone know lower or upper bounds, constructive or not, for the preprocessing phase given $O(\log n)$ query time?

I'm working in two dimensions, and the points have floating point coordinates (i.e., not integer coordinates).

---

My algorithm is similar to a standard algorithm and has similar performance characteristics. I discovered it independently so it differs in some immaterial ways but it's not original. It works as follows:

Preprocessing:

1. Translate polygon into first quadrant. (This is to simplify later calculations but isn't strictly necessary.)
2. Create a ray passing from the origin through every endpoint and intersection point of an edge. In each resulting cone no edge crosses another.
3. For each cone, sort the edges crossing that cone by their distance from the origin.

Online:

1. Apply the same translation to the query point as was applied to the polygon.
2. Using binary search, find the cone containing the point, or if none, return false.
3. Using binary search, find the number of edges in the point's cone for which the point and origin are on the same side. Return whether this number is odd.