PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Prob_Solve
[問題] 計算幾何 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
繼續閱讀
[請益] 算每個星期三是幾號
final01
Re: [問題] 計算幾何 - stabbing line
Leon
Re: [問題] 計算幾何 - stabbing line
DJWS
[問題] 計算幾何 - stabbing line
FRAXIS
[問題] 請教有關時間複雜度的考題
Sunofgod
[請益] 請問 Maximum Fuzzy Partition
r94098
Re: [問題]n位整數拿掉m數字得到最大數值
nilson847552
Re: [問題]n位整數拿掉m數字得到最大數值
stimim
Re: [問題]n位整數拿掉m數字得到最大數值
CaptainH
Re: [問題]n位整數拿掉m數字得到最大數值
Leon
Links
booklink
Contact Us: admin [ a t ] ucptt.com