怎樣獲取三維點集中平均距離最大的四個點？

01-29

說明三維點集即每個元素
點a(x,y,z) 每個點都有三個坐標值
給定一個點集A A中有n個點每個點的坐標值都不相同

怎樣找出這個點集之中平均距離最遠的四個點
平均距離的定義：這四個點構成的三稜錐的邊長的和

這個問題叫做maximum dispersion問題, 其中你要解決的特殊case. 從cite這個paper http://arxiv.org/abs/cs/0310037 的其他paper來看, 似乎沒人知道比 $Omega(n^4)$ 好的演算法. 當然更有可能是沒有人特別關心這個特殊的例子.

平面版本(2D點集平均距離最大的3個點)可以 $O(nlog n)$ . 先找凸包(最優解一定三個點都在凸包上), 然後用這裡面描述的方法: 如何計算凸包的最大內接四邊形面積?

3/29/2017 更新: 和 Timothy M. Chan 討論了一下.

$ilde{O}(n^{4-1/3})$ 應該是是可行的. 需要以下的一個數據結構:

數據結構1: Preprocess n個點, 使得query任意三個點a,b,c. 找到一個點p, 使得d(a,p)+d(b,p)+d(c,p)最小.

這樣演算法的時間複雜度=preprocessing時間+和測試所有3個點的可能性. 如果preprocessing時間是p(n), query時間是q(n). 我們獲得時間複雜度 $O(p(n)+n^3 q(n))$

數據結構1需要一個更簡單的數據結構.

數據結構2: Preprocess n個點, 使得query任意三個點a,b,c和一個r. 找到一個點p, 使得 $d(a,p)+d(b,p)+d(c,p)leq r$ , 或者表示沒有這樣的p存在.

我們可以測試平均距離是否不到r, 可以看出這是在 $mathbb{R}^3$ 中的semialgebraic set range search. (恩, 因為滿足 $d(a,p)+d(b,p)+d(c,p)leq r$ 這樣的集合是semialgebraic的, 而我們return的點p是 $mathbb{R}^3$ 里 ) 所以直接用[1208.3384] On Range Searching with Semialgebraic Sets II .

然後對於 $r$ 做parametric search, 多一個polylog factor就能得到數據結構1.

更好的演算法應該存在, 上述文獻目標是最小的空間. 但是我們演算法問題不用考慮空間, 所以可以balance一下preprocessing time和query time. 似乎 $ilde{O}(n^3)$ 應該也是可行的. 需要仔細看文獻. 如果我沒有理解錯, 利用 https://users.cs.duke.edu/~pankaj/publications/surveys/srs.pdf 這裡面第14頁的空間的描述,

https://users.cs.duke.edu/~pankaj/publications/papers/semi-range.pdf 和這裡面第397頁里對於時間和空間的關係的描述. 可以推出這樣的演算法是存在的.

如果高維版本可以接近線性時間獲得 $1+epsilon$ 的近似解, 是個好的研究問題. 因為幾何里一般要最大化的東西, sampling就沒啥用了. 平均距離也比最大距離, 容量之類的難搞多了.