1. PTT
  2. 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
继续阅读
[请益] 算每个星期三是几号final01Re: [问题] 计算几何 - stabbing lineLeonRe: [问题] 计算几何 - stabbing lineDJWS[问题] 计算几何 - stabbing lineFRAXIS[问题] 请教有关时间复杂度的考题Sunofgod[请益] 请问 Maximum Fuzzy Partitionr94098Re: [问题]n位整数拿掉m数字得到最大数值nilson847552Re: [问题]n位整数拿掉m数字得到最大数值stimimRe: [问题]n位整数拿掉m数字得到最大数值CaptainHRe: [问题]n位整数拿掉m数字得到最大数值Leon

Links booklink

Contact Us: admin [ a t ] ucptt.com