作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 计算几何 Closest Pair Decision Problem
时间Sat Dec 7 00:29:49 2013
给定在平面上n个点的集合P及一正实数x，设计一线性演算法判断x是否大於
P中最靠近两点之距离。
我的解法无法满足algebraic decision tree model，不知道有没有办法
设计出一个满足algebraic decision tree model的演算法。
（只能用+-*/等代数运算和比较）
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 129.170.195.150
1F：推 seanwu:应该不行，Integer element distinctness Ω(nlogn) 12/08 15:58
2F：→ seanwu:可以reduce到你的问题: 给n个整数a1,a2,...,an问是否皆相异 12/08 16:00
3F：→ seanwu:=> 平面上取(a1,0),(a2,0),...,(an,0)和x=0.5 12/08 16:00