[問題] 計算幾何 Closest Pair Decision Problem

作者: FRAXIS (喔喔)   2013-12-07 00:29:49
給定在平面上n個點的集合P及一正實數x,設計一線性演算法判斷x是否大於
P中最靠近兩點之距離。
我的解法無法滿足algebraic decision tree model,不知道有沒有辦法
設計出一個滿足algebraic decision tree model的演算法。
(只能用+-*/等代數運算和比較)
作者: seanwu (海恩)   2013-02-08 15:58:00
應該不行,Integer element distinctness Ω(nlogn)可以reduce到你的問題: 給n個整數a1,a2,...,an問是否皆相異=> 平面上取(a1,0),(a2,0),...,(an,0)和x=0.5

Links booklink

Contact Us: admin [ a t ] ucptt.com