请教一个困扰多年未找到思路的问题
有一个不规则图形(比如某国、某省地图),如何找到一个直径最小的圆把这个图形完整包含在这个圆里面?
分不多了,希望大家不要介意
[解决办法]
凸包的最小外覆园,这个不至于困扰很多年吧,暴力也就O(n^3)
事实上这个是有O(n)的解法的
http://en.wikipedia.org/wiki/Smallest_circle_problem
发布时间: 2012-07-31 12:33:46 作者: rapoo
请教一个困扰多年未找到思路的问题
有一个不规则图形(比如某国、某省地图),如何找到一个直径最小的圆把这个图形完整包含在这个圆里面?
分不多了,希望大家不要介意
[解决办法]
凸包的最小外覆园,这个不至于困扰很多年吧,暴力也就O(n^3)
事实上这个是有O(n)的解法的
http://en.wikipedia.org/wiki/Smallest_circle_problem