请教一个计算几何的问题
给定两个点集A和B，问能否找到一个圆，这个圆包含所有的A中的点，不包含任何B中的点，如果能找到的话，找到这个点(可以给出圆心和半径或者其他方式给出也可以)
作者: ji414341055 发布时间: 2011-05-26
大家帮帮忙啊，没有具体算法说一下大体思路或者想法也好哇！～谢谢大家了。。。
作者: ji414341055 发布时间: 2011-05-26
可不可以这样做，先求出点集A的凸包，然后检查B中每一个点是否在这个凸包内，在的话那么这个圆不存在。否则找凸包的最小包围圆。但是这样复杂度很高啊，有没有更好的算法？
作者: ji414341055 发布时间: 2011-05-26
包含A中所有点的最小圆，应该就是这些点围成的最小正方形的内接圆和最小外接圆之间。但是其圆心可知就是正方形的中心，然后计算所有B中点到该圆心的距离中的最小值，如果小于内接圆半径则找不到解，如果大于外接圆半径，则外接圆就是所求结果，否则，还需要计算A中所有点到该圆心的最大值，如果其值比B中计算的最小值小，这有解，否则无解
作者: wcyoot 发布时间: 2011-05-26