Блог пользователя Petr

Автор Petr, история, 8 лет назад, По-английски
  • Проголосовать: нравится
  • +102
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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?)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    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 :)

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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.