主题：求一个算法 -- 东方射日
共:💬55 🌺26
计算凸包的算法我了解，复杂度是O(NLogN)
但是求空间中最远点对的算法我就不是很懂了。如果对点不处理的话，只能两两计算，那么复杂度是O(N^2)。如果那样的话，第一步找凸包就根本没有必要。
不过据说如果是凸包上的点，那么寻找他们间最远点对的复杂度就下降到3N，也就是O(N),上网搜了下，号称叫Sharmos's algorithm。不过没有找到具体的介绍，这里就偷偷懒，你给介绍下哈。
- 相关回复 上下关系8
🙂算法有错 东方射日 字459 2009-01-09 13:52:00
🙂你说的对，果然有错 温雅颂 字34 2009-01-09 14:23:58
🙂其实我们很接近一个O(N^2)的算法了 东方射日 字924 2009-01-09 18:45:42
🙂追风兄对具体算法能说下
🙂有人算过了 三力思 字167 2009-01-09 11:24:15
🙂放弃，彻底投降 1 沉宝 字1159 2009-01-08 13:03:01
🙂算法不正确 东方射日 字220 2009-01-09 18:26:41
🙂直接用X,Y最大,最小的方块.求对角线,得出圆心? 三力思 字28 2009-01-08 13:31:18