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

History

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