algorithm for largest radius of a circle inside a given polygon

Правка en2, от 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.

Теги algorithm, geometry

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский kowalsk1 2018-04-14 03:57:24 15 Tiny change: ', but any code is welcome. ' -> ', but any references are welcome. '
en1 Английский kowalsk1 2018-04-14 03:56:42 388 Initial revision (published)