RANDOMIZATION YIELDS SIMPLE <i>O</i>(<i>n</i> log<SUP>☆</SUP> <i>n</i>) ALGORITHMS FOR DIFFICULT Ω(<i>n</i>) PROBLEMS

作     者：Devillers, Olivier 

作者机构：INRIA F-06561 Valbonne France 

出 版 物：《INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS》 (国际计算几何学与应用杂志)

年 卷 期：1992年第2卷第1期

页      面：97-111页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ESPRIT 

主　　题：Randomized algorithms influence graph conflict graph skeleton of a polygon Delaunay triangulation euclidean minimum spanning tree 

摘      要：We use here the results on the influence graph(1) to adapt them for particular cases where additional information is available. In some cases, it is possible to improve the expected randomized complexity of algorithms from O(n log n) to O(n log(star) n). This technique applies in the following applications: triangulation of a simple polygon, skeleton of a simple polygon, Delaunay triangulation of points knowing the EMST (euclidean minimum spanning tree).