Petr's blog

A half-plane week
By Petr, history, 8 years ago, In English

http://petr-mitrichev.blogspot.com/2016/07/a-half-plane-week.html

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

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I haven't seen that randomized algo to intersecting halfplanes earlier, but I think it's worth noting that main idea is almost the same as in Smallest Enclosing Circle problem (does there even exist deterministic algo with similar complexity?)

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

    Yes, it's quite similar. I'm surprised you didn't see this one before — I had the feeling of being the last one to the party when I learned about it :)

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

      Maybe that's because I am quite satisfied with online half-planes intersection working in that pompon left in our library :).

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

        Can you please share your library here ?

        → Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I think that I know a different solution to the half-plane problem. Instead of doing binary search, let the value gradually decrease and look at the polygon where O must be located. Initially, when , this polygon is the same as the input polygon. When the value is decreased, the sides move inwards at constant speed which can be determined in linear time using rotating calipers algorithm. The lengths of the sides decrease linearly, so it is possible to find the times when each length would reach zero. When the length of a side becomes zero, adjacent sides will begin shrinking faster, so it is necessary to emulate this process and to recompute the times for adjacent sides when one of the sides disappears. This can be easily done in time using a heap. So, this solution works in time, doesn't use binary search and is completely deterministic.

→ Reply