4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Actually I see Sarnak and Tarjan's paper Planar Point Location Using Persistent Search Trees solves a related problem with $O(n)$ space, $O(n \log n)$ time, and $O(\log n)$ query time. However it works with polygonal subdivisions. I think that adapting it to the setting of non-simple polygon containment would introduce an extra factor of $n$ in time and space. $\endgroup$ – Solomonoff's Secret Jun 22 '16 at 18:39
  • $\begingroup$ So maybe you could edit the question and if you found the solution answer it yourself? $\endgroup$ – Evil Jun 22 '16 at 19:04
  • $\begingroup$ @EvilJS The translation isn't entirely trivial and I would like time to check the details but when I have the time, I will update the question. $\endgroup$ – Solomonoff's Secret Jun 22 '16 at 19:15
1
$\begingroup$

Your problem is a special case of planar point location. The algorithm/data structure you found by Snarak and Tarjan can answer point location (and thus point in polygon) queries in $O(\log n)$ time using $O(n \log n)$ preprocessing and $O(n)$ space. That is optimal. There are two other data structures that achieve this: a data structure by Kirkpatrick and a randomized incremental approach. The randomized incremental approach can be improved to $O(n \log^* n)$ expected preprocessing time in case of a simple polygon, and is fairly simple besides.

$\endgroup$
  • $\begingroup$ I believe this is correct. The reduction from point in polygon to point location preserves $n$ and so the bounds from the latter problem apply directly to the former. $\endgroup$ – Solomonoff's Secret Jul 2 '16 at 21:12
  • $\begingroup$ Note: this answer is not actually correct. The reason is because a self-intersecting polygon with $n$ vertices can have $\theta(n^2)$ edge intersections and so an input of point-in-polygon of size $n$ translates to an input of point-location of size $\theta(n^2)$ in the worst case. This is what I was concerned about in the comment under my question. I will have to add a separate answer. $\endgroup$ – Solomonoff's Secret Jul 5 '16 at 14:32
0
$\begingroup$

I am posting this answer because Noinia's answer does not account for how the input size changes when reducing Repeated Point In Polygon to Planar Point Location.

Sarnak's and Tarjan's paper Planar Point Location Using Persistent Search Trees solves a related problem, the Planar Point Location problem, with $O(n)$ space, $O(n \log n)$ preprocessing time, and $O(\log n)$ query time. We can reduce Repeated Point In Polygon to Planar Point Location by first computing all edge intersections of the input polygon and passing all the vertices and edge intersections to the Planar Point Location algorithm. In the worst case this reduction grows the input size from $\theta(n)$ to $\theta(n^2)$ and thus Sarnak's and Tarjan's algorithm yields $O(n^2)$ space, $O(n^2 \log n)$ preprocessing time, and $O(\log n)$ query time.

The space and preprocessing time of the above algorithm are likely not optimal because they don't take advantage of the special structure of the intersection points with respect to the vertices.

$\endgroup$
  • $\begingroup$ Can you edit this to phrase it as a self-contained answer to the question, instead of as an extended comment/response on Noinia's answer? It looks like you have identified an answer to your question (question: can you do better than $O(n^3)$ preprocessing and $O(\lg n)$ query time? answer: yes, you can achieve $O(n^2 \lg n)$ preprocessing time and $O(\lg n)$ query time), so it would be best to write it from that perspective, in a self-contained way that doesn't require reading Noinia's answer to understand. $\endgroup$ – D.W. Jul 6 '16 at 2:56
  • $\begingroup$ Then, post a detailed comment on Noinia's answer that identifies the error/flaw in that answer. Don't use answers to comment on or respond to other answers. (This isn't a discussion forum; we want answers to be reserved solely for material that answers the question that was answered.) Thank you! $\endgroup$ – D.W. Jul 6 '16 at 2:57
-1
$\begingroup$

I have an algorithm O(log(n)) for this purpose that uses a kind of special data structure that sorts the sides of the polygon when is being created to avoid preprocessing. This sort procedure is executed in O(n*log(n)).

$\endgroup$
  • $\begingroup$ Could you please elaborate? How do you sort the sides of the polygon? $\endgroup$ – Solomonoff's Secret Jul 27 '17 at 14:28
  • 1
    $\begingroup$ Can you describe your algorithm? As it stands, this doesn't answer the question; it merely claims that an answer exists. Please edit the question to describe your algorithm. $\endgroup$ – D.W. Jul 27 '17 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.