作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 计算几何 Closest Pair Decision Problem
时间Sat Dec 7 14:06:31 2013
※ 引述《FRAXIS (喔喔)》之铭言：
: 给定在平面上n个点的集合P及一正实数x，设计一线性演算法判断x是否大於
: P中最靠近两点之距离。
: 我的解法无法满足algebraic decision tree model，不知道有没有办法
: 设计出一个满足algebraic decision tree model的演算法。
: （只能用+-*/等代数运算和比较）
感觉很难达成线性时间...
我猜你的解法，应该是把平面切割成宽度为x的正方形网格
（上左边界是闭区间、下右边界是开区间）
一、不相邻的网格，距离一定超过x，没有检查的必要！
二、检查网格内部，若超过三个点，就一定有「距离小於x的点对」，演算法结束
若不超过三个点，需要检查的点对，顶多3对，是常数
三、检查相邻八个网格：每个网格现在顶多三个点，需要检查的点对，顶多3*3*8对，常数
然而如何把每一个点归类於正确的网格呢？
这件事情本质上跟排序很相像
然而排序是 omega(nlogn)
所以我觉得很难达成线性时间
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.250.62.191
※ 编辑: DJWS 来自: 111.250.62.191 (12/07 14:15)
1F：推 singlovesong:这就跟先找closest pair 在看是不是大於x一样lol 12/07 15:00
2F：推 FRAXIS:这就是我用的方法，所以需要用floor运算 + Hash 12/07 17:42
3F：推 seanwu:这件事比sort简单很多才对XD... 你只需要知道相邻而已 12/08 16:17
4F：→ seanwu:现在的问题是不用floor没办法决定是哪一格 12/08 16:20
5F：→ seanwu:相邻的话用hash查就够了 12/08 16:21
6F：→ DJWS:不用floor的话，一种方式是把网格格点上的数字，掺进去排序 12/08 20:43
7F：→ DJWS:所以我才会觉得这跟排序差不多 12/08 20:43
8F：推 neutrino:若不用hash, 题目改成一维, 有O(n)演算法吗? 12/09 20:11
9F：推 FRAXIS:在algebraic decision tree model下 12/09 20:43
10F：→ FRAXIS:就算是一维的也是有n lg n的下限 12/09 20:43