n********n
发帖数: 529 | 1 3维空间有若干个点，求一平面包含最多的点。被 A家问道这个题，没回答好。 |
n********e
发帖数: 518 | |
n******n
发帖数: 567 | 3 Reduce to 4Sum. O(n^2) if you can find unique identifier for a line.
Is this from phone or onsite?? Seattle?? |
n********n
发帖数: 529 | 4 能不能展开说说？ 看了http://en.wikipedia.org/wiki/RANSAC，还是没头绪呀。
【在 n********e 的大作中提到】
: RANSAC
|
n********n
发帖数: 529 | 5 怎么能 reduce 到 4sum呢？我现在还没想清楚已知一个面怎么才能判断另外一个点是
否在这个面上。
是onsite问的。湾区。感觉这题有点刁难我了。
【在 n******n 的大作中提到】
: Reduce to 4Sum. O(n^2) if you can find unique identifier for a line.
: Is this from phone or onsite?? Seattle??
|
a******a
发帖数: 2646 | 6 三重循环咋样
设点集合S
for each point1 in S
for each point2 in S一{S1|point1 已试过的点}
for each point3 in S一{S1|point1 已试过的点}一{S2|point1 已试过的点}
算出在 point1 point2,point3决定的平面的点数
|
C***U
发帖数: 2406 | 7 那个不是精确解 我觉得不适用于你这个题目
【在 n********n 的大作中提到】
: 能不能展开说说？ 看了http://en.wikipedia.org/wiki/RANSAC，还是没头绪呀。
|
n******n
发帖数: 567 | 8 我说的是假入你可以用hash存储line的话，可以O(n^2)时间，for each line get hash
code, then put into a hashtable. Then for each line, check if there is hash
match(the two form a plane). The problem is there seems no way to do this O
(1) time.
所有大概要用三重循环。但是另一个问题就是你怎么表示line,因为scope and
intersect is double. 还是没法hash. 所有就是排序的O(n ^ 3 lg n)算法。
但应该有一个O(n^3)算法， 懒得想了，这题不会真让做到那种地步吧。。。。。
这有有paper， 是关于三点贡献reduce到3sum的，并说明是N^2 hard 问题。
http://igitur-archive.library.uu.nl/math/2006-1215-200814/gajentaan_93_n2-hard.pdf
【在 n********n 的大作中提到】
: 怎么能 reduce 到 4sum呢？我现在还没想清楚已知一个面怎么才能判断另外一个点是
: 否在这个面上。
: 是onsite问的。湾区。感觉这题有点刁难我了。
|
h*******e
发帖数: 1377 | 9 3點確定一面。。然後把參數標準化之後轉換成面的方程 hash 求hash 上 count最多的面
n點枚舉3點 O(N^3) hash O(1)
乘起來總共 O(N^3) |
h*******e
发帖数: 1377 | 10 照你說法， 兩點一直線O(n^2) 兩條直線一個 平面 應該是 O(n^4)
hash
hash
O
【在 n******n 的大作中提到】
: 我说的是假入你可以用hash存储line的话，可以O(n^2)时间，for each line get hash
: code, then put into a hashtable. Then for each line, check if there is hash
: match(the two form a plane). The problem is there seems no way to do this O
: (1) time.
: 所有大概要用三重循环。但是另一个问题就是你怎么表示line,因为scope and
: intersect is double. 还是没法hash. 所有就是排序的O(n ^ 3 lg n)算法。
: 但应该有一个O(n^3)算法， 懒得想了，这题不会真让做到那种地步吧。。。。。
: 这有有paper， 是关于三点贡献reduce到3sum的，并说明是N^2 hard 问题。
: http://igitur-archive.library.uu.nl/math/2006-1215-200814/gajentaan_93_n2-hard.pdf
|
