qwerty787788's blog

Easy online point location algorithm
By qwerty787788, 2 years ago, In English

In the hardest problem of Meta HackerCup 2022 Round 3 it was needed to write an algorithm for fast points locations. Basically, you were given a lot of polygons and a lot of points. For each point, you need to find the smallest polygon, which contains it. In the hardest version of the task, points are created based on previous answers, so you can't solve it offline.

I believe everybody who solved this problem during the contest used the same algorithm with sweep-line and persistent treap (or just std::set, but it doesn't work for online version of the task).

After the contest PavelKunyavskiy told me that it is possible to solve this task with just a segment tree (but the complexity is $$$O(\log^2 n)$$$ per query). I haven't seen this algorithm before, so I wrote an explanation of it here: https://teletype.in/@bminaiev/online-point-location.

Also after a discussion with izban I think it is possible to improve the complexity of the algorithm with fractional cascading, but it is not very straightforward (and will work slower in practice).

  • Vote: I like it
  • +191
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +40 Vote: I do not like it

I did the same, because I've never implemented the sweep-line with segments and got scared of it (so I wanted to work with something static), but after the round I thought longer about it and I actually think that the sweep-line might be a bit easier if you have a general function to compare two segments with non-empty intersection of projections to OX line (and anyway it's convenient to have it implemented).

So I guess it comes mostly to the data structure you use. std::set might be problematic because you don't have full control on what's happening inside. BST sounds better, but making it persistent always requires being extra focused, so there are some trade-offs.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Yeah, agree, both versions require the same function to compare two segments, so the difference is the data structure, where segments are stored. In my case I just really don't like manually implementing BST (even not persistent versions), so to me it looked like a clear win.

    But if you have a persistent treap code in the library, or remember how to implement it fast, the sweep-line could be easier.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

WOW, E1 is quite old, I saw convex offline version longtime ago. I even created non-convex offline version: https://www.hackerearth.com/practice/math/geometry/line-sweep-technique/practice-problems/algorithm/simple-polygon-eadaf4dd/.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, the problem itself is pretty classical. Does convex property actually help here in any way?

    By the way, thanks for the link to your problem, now I can fix my algorithm to handle the case when points are allowed to be on the boundaries.

    → Reply