algorithm for largest radius of a circle inside a given polygon

Revision en2, by kowalsk1, 2018-04-14 03:57:24

Does anyone know an algorithm to solve the following problem:

Given a sequence of points in the plane that represent a polygon (not necessarily convex), output the maximum possible radius of a circle that can fit inside this polygon.

It would be good if it was below O(n2), but any references are welcome. Thanks ahead.

Tags algorithm, geometry


  Rev. Lang. By When Δ Comment
en2 English kowalsk1 2018-04-14 03:57:24 15 Tiny change: ', but any code is welcome. ' -> ', but any references are welcome. '
en1 English kowalsk1 2018-04-14 03:56:42 388 Initial revision (published)