Need help on Rotating Calipers technique

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

Автор arbitrary_A, история, 8 лет назад, По-английски

i tried to learn this technique from this blog.. but i couldn't understand it clearly from this mentioned site..so need some good blogs on this! you may also add related problems...

thanks in advance!

computational geometry,, rotating calipers,, convex hull

arbitrary_A
8 лет назад
6

Комментарии (6)

Написать комментарий?

honganptnk1518

8 лет назад, скрыть # |

+21

Before you conduct any further research, I have to warn you that the technique was proven wrong in finding the largest triangle in a convex https://mirror.codeforces.com/blog/entry/52341.

→ Ответить

arbitrary_A

8 лет назад, скрыть # ^ |

thanks for your kind information :)

→ Ответить

cbosch_carlgauss

8 лет назад, скрыть # ^ |

Maybe is wrong for that problem but is useful and proven truth for other problems, like fartest pair of points on a cloud, polygon width, minkowski sum of polygons, convex hull of two convex polygons, etc.

All this problems turn to be linear with this technique.

I recently solved a problem of fartest pair of point under other metric using rotating calipers

But is good to know problems that cannot be solved that way. Thanks

→ Ответить

arbitrary_A

8 лет назад, скрыть # ^ |

your(cbosch_carlgauss) mentioned problems can't be solved without this way?? i meant alternate solutions except this technique??

→ Ответить

cbosch_carlgauss

8 лет назад, скрыть # ^ |

← Rev. 2 →

Yeah, result that mostly of that problems can be done in O(NlgN) or O(Nlg²(N)) time, but with rotating calipers you can archive O(N) time, assuming convex hull is done.

It seems not to useful but others solutions depens on binary searches and others things that make the code difficult to implement and rotating calipers take short coding.

→ Ответить