h****r
发帖数: 258 | 1 Swarowski designs and manufactures the world's most beautiful jewelry for
the most beautiful people.
When Kmart, Sears, and Nordstrom decided to evict Ivanka Trump branded
jewelry from their U.S. online stores, Swarowski seized the opportunity and
asked Ms. Trump to design exclusively for Swarowski for the next four years.
The upcoming Ivanka Trump jewelry collection uses quite disruptive
technology, namely (a) 3D printing which is a challenge as the material used
is gold powder, (b) Rhino as a ... 阅读全帖 |
|
o*****e
发帖数: 23 | 2 对于三维非凸多面体模型, generalized voronoi diagram是需要高阶曲面来表示的. 问
题是与多面体相接的voronoi diagram的部分是否为平面?
谢谢! |
|
D*******r
发帖数: 37 | 3 how to compute the farthest-point voronoi diagram in O(nlogn)?
Is there any way similar to the forturne algorithm for the nearst-point
voronoi diagram?
Thanks! |
|
l*****g
发帖数: 49 | 4
yes, the farthest-point voronoi diagram can be computed in time
O(n log n), by any optimal algorithm for 3D convex hull (not
a plane-sweep algorithm similar to fortune's)
take any classical textbook in computational geometry and you will
find the following information (for example, Shamos and Preparata's):
the farthest-point voronoi diagram (in the plane) is the projection
of the lower envelop of n (special) planes in 3D. The lower envelop is in fact
the dual of a convex hull, so any optimal co |
|
x***u
发帖数: 336 | 5
问
what do you mean by 与多面体相接的voronoi diagram的部分? |
|
v***a
发帖数: 365 | 6 来自主题: JobHunting版 - 问一道题目 或许可以这样：
构造 Voronoi Diagram, O(NLogN) 可以构造出来
Voronoi 最多有 3N 条边
求每个点最近的点，只需要检查每条 voronoi的边，O(2 * 3N )
求每个点最近的2个点，除了检查每条边，还要检查，离他最近点的所有voronoi的边，
O(? * 3N), ? is constant,
求最近的3个点，还要检查第二近的点的所有边，以及第一近的点的所有voronnoi的边
，可以证明肯定在这些边里，O(? * 3N), ? is also constant.
Anyway, O(NLogN）
请问你面的什么公司？
这种计算几何的题目，估计 G/FB 也不会考的吧，做地图的公司？
如果还有position的话，也想投一下试试，
投了无数公司，现在一个面试都没有……杯具啊 |
|
N**G
发帖数: 392 | 7 真是大开眼界啊！
从这个材料可以找到为什么恽老师发表的会议论文和期刊论文的署名不同，比如为什么
Xiaolei Bai只出现一次！
恽老师在文中提到： “在指导你论文写作之前，我已经与我们论文的部分合作者以
及其他人通过讨论班或者电子邮件清清楚楚讲过我对于定理1的猜想与证明思路，这些
电子邮件与讨论班的同仁可以成为我的物证与人证。”
希望恽老师尽快公布这些邮件！
恽老师5月7日给戈鋆的《解释与答复》
一个理论成果，在完成其严格证明以前，还不能称为定理，而只能够称为猜想。因此，
对一个理论成果的取得，要谈贡献，只应该从两个方面考虑：
1. 猜想是由谁提出的？
2. 谁完成了证明，使猜想变成定理？
而对于证明比较困难的定理，其证明，往往分为两步：（1）证明思路、总体框架与主
要证明步骤的设计；（2）根据设计好的思路、总体框架与证明步骤进行严格的、细致
具体的验证推导。
根据国际学术界的惯例，对一个成果，论主要贡献，应该是对上面的1与2（2）作出贡
献者。这方面最有说服力的例子是前几年轰动国际数学界的庞家莱猜想的证明。猜想是
庞家莱提出的，而证明思路、总体框架与主要证明步骤是... 阅读全帖 |
|
h**********c
发帖数: 4120 | 8 其实物理也就是中医，你能看到的就是你能看到。
可能人类看到的就是就是自己的行为在自己的那个voronoi cell壁上的投影。就像自己
看到自己的瞳孔上的眼屎。
每一个voronoi cell可能都有自己的一套物理定律。所以不能擅越。
中医可能也是这么说的吧。
我说的都是可能。 |
|
w***g
发帖数: 5958 | 9 大牛不敢当。
是圆形对应的像素连成的图。确定R画出来的圆里面的像素不一定正好是16n，有可能除
不尽。那样的话不同颜色的像素最多差一个。
你的hamilton cycle+16个vertices思路有点混乱。剪刀走16步，步与步之间会交叉，
切出来的未必是16片。距离相等这个idea倒似乎可以。先均匀放入16个不同颜色的点，
其余的点没有颜色，然后让颜色以相同的速度扩散，不同的颜色碰到的地方就是边。出
来的是一个voronoi图。如果16个点位置放的好的话，就可以保证16块大小一样。
话说，如果精度无穷，能否证明最优切法一定对应一个voronoi图？我看着似乎可以。
length/ |
|
m*l
发帖数: 507 | 10 对于算法懂的很少，如果能说一下为什么要算这个，可能会找到更多的解决方案。GIS
有很多常用的算法做各种优化。比如
Voronoi diagram
解决的是下面的问题，有几个商店分布在城市当中，划分每一个商店的服务范围。
看看VORONOI DIAGRAM的算法，也许有点希望吧。 |
|
a*******8
发帖数: 32 | 11 可考虑对多边形图层作Voronoi Diagram, 所得结果除了Voronoi polygons外，还有一
个distance raster (假设取名为DisRaster). 每个居民地址点在DisRaster上所对应的
像元值就是你要算的最短距离。计算200点只需3-4秒。17，000个polygon也不会花太多
时间。我在ESRI Scripts 看到这个extension, 可以下载试试。有问题欢迎来信交流。
http://arcscripts.esri.com/details.asp?dbid=15481 |
|
|
z*j
发帖数: 42 | 13 来自主题: JobHunting版 - 问个算法题 I am not very sure about this problem. Just some thoughts using voronoi
diagram in computation geometry. |
|
l***i
发帖数: 1309 | 14 voronoi diagram, O(nlogn) but it is too difficult for interview questions
unless you work on computational geometry. |
|
n*******w
发帖数: 687 | 15 这个适合面试的答案。每个点上计算出所有距离排序。
Voronoi diagram，KD tree，Range tree可以在follow up中提到。半个小时白板
coding实现几乎完全不可能。 |
|
|
|
|
s****0
发帖数: 117 | 19 我不知道答案。但是Voronoi diagram不太对头。 |
|
a***y
发帖数: 852 | 20 另外，从实用技术考虑来讲
如果kmeans不知道如何指定K，可以用Hierarchical clustering。复杂度高但是一次能
得到整个hierarchy。可以从中选择合适的cluster粒度。X-means指定K的方法没有用过
，不过好像比较流行。我需要去看一看。。。
KNN最大的瓶颈是O(n) complexity。但是KNN的solution space其实是对空间的voronoi
划分。random forest本质上也是对空间的划分。应该是取代KNN最理想的直接选择。 |
|
a***y
发帖数: 852 | 21 另外，从实用技术考虑来讲
如果kmeans不知道如何指定K，可以用Hierarchical clustering。复杂度高但是一次能
得到整个hierarchy。可以从中选择合适的cluster粒度。X-means指定K的方法没有用过
，不过好像比较流行。我需要去看一看。。。
KNN最大的瓶颈是O(n) complexity。但是KNN的solution space其实是对空间的voronoi
划分。random forest本质上也是对空间的划分。应该是取代KNN最理想的直接选择。 |
|
y***u
发帖数: 101 | 22 Yes you can. Can be reduced to 3D convex hull. |
|
h**********c
发帖数: 4120 | 23 From my limited experience,
1. computer graphics 大量使用mesh simplification (LOD), Delanay
triangulation, 3d sorting, BSP 啦 很多.
2. 比较n的, 用Voronoi diagram 解3维以上的ode system.
有很多东西,没办法划那么细粉. |
|
w***n
发帖数: 1084 | 24 Actually if just in 2D/3D, you probably can try a Delaunay triangulation too, and your nearest neighbor shouldn't be too far away from the neighborhood in the triangulation.
It is easy to prove that the nearest neighbor $B$ of $A$ should be in $A$'s neighborhood in the triangulation.
Because if it didn't, you can always find a triangle that is made of $A$ and its two neighbors containing $B$, which violates the Delaunay (voronoi) property. |
|
c*****t
发帖数: 1879 | 25 用 Delaunay triangle / Voronoi diagram 的话应该可以更快。光算
triangle / diagram 的话是 O (n log n)。
对于每个点搞定 k 个 neighbor 花的时间应该是 O (k)。因为你这个 k 是
constant，所以总共是 O (n log n) |
|
a*******8
发帖数: 32 | 26 除了上面提到的Voronoi方法外，用ArcGIS对两个图层进行spatial join也可解决此问
题。离多边形最近的点的属性将被赋予该多边形，同时将产生新的field存储点到多边
形的距离。 |
|
f******r
发帖数: 2975 | 27 I have one n dimensional lattice L
the minimal norm of the lattice is (2d)^2
Let d be the radius of an n dimensional sphere
to me it is obvious that
the volume of this sphere
<= the volume of the lattice voronoi cell
but someone says that I have to prove it
I wonder how
thanks a lot |
|
r******l
发帖数: 10760 | 28 我其实没有什么猜想，应该说是问题更合适。有一片发表的文章提出了一个方法计算
Voronoi diagram，虽然会有错误，但是错误很少。我希望能够从数学上给出一个错误
的期望值。该方法很简单，就像小时候常见的数字游戏，但是实际分析起来估计要用整
数数论的知识，我是一窍不通。所以希望最好能有个这种求助网站，能有有兴趣又有该
方面知识的人能解决。对专业人士来讲易如反掌也说不定。 |
|
|
A*******r
发帖数: 768 | 30 没你的文章就不看了
从你的描述讲几句
如果不对那就忽略
1 你的算法的复杂度，因为有算法可以算到精确解，你的算法的优势在哪里？
速度快？快到何种程度
2 你的算法就是个heuristic method, 你算出来的结果质量如何？
衡量结果质量的简单方法是你可能拿到的最坏结果跟正确结果的差距
比较难的是平均差距
比较的话一般取决于距离的定义
3 你的算法多大程度上能够找到正确解，
这个一般情况下用统计的方法，把benchmark data搞一遍
或者有针对你的问题的方法
4 你用正确性换来的速度到底能不能在实际中不影响后续问题的解决
不能的话就是纸上谈兵，但是这个问题也很难讲清楚
很多算法都是自己吹自己的
你的问题在 2 和 3。就是一个近似解评估和算法评估
常规问题，还没到猜想那么吓人的地步
找些图论，算法的相关东西看看
这个算法是用来求discrete Voronoi diagram的。有很多算法可以保证准确答案的，跟
那些准确答案比一下就知道哪些点是错误的了。文中是通过大量的实验得到错误很少这
个事实的。
具体文章在这里可以看到：
http://portal.acm.org/c |
|
m****t
发帖数: 570 | 31 又比较仔细得看了一下
Ge Jun的工作应该只和paper中的Lemma 4.1有关
但Lemma 4.1确实不是Ge Jun提出来了，Lemma 4.1提的是12种，而不是Ge Jun提出的22种
Lemma 4.1: There are 12 types of congruent Voronoi tessellations.
其实Lemma的证明不提供不会影响到整篇paper（CS的paper很多Lemma都是不给证明的，
给的话也只是放在appendix里供参考，读者不看不会影响到对整篇paper的理解）
所以这篇paper没有给Ge Jun 一个coauther应该是没什么问题的
当然最好是应该在paper中写上Lemma 4.1的证明用到了Ge Jun提出的证明技巧（把Ge
Jun的本科毕业论文作为Technical Report引一下），nice的老板也是会把学生加成
coauther
当然图的抄袭是另一回事，不过一图是重新画过的，没有直接copy，二Yun作为Ge的指
导老师对图表、数据有没有使用权？ |
|
