Published in

World Scientific Publishing, International Journal of Computational Geometry and Applications, 01(02), p. 97-111

DOI: 10.1142/s021819599200007x

Links

Tools

Export citation

Search in Google Scholar

RANDOMIZATION YIELDS SIMPLE O(n Log⋆ N) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS

Journal article published in 1992 by Olivier Devillers ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

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 ? 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). Keywords: Randomized algorithms, Influence graph, Conflict graph, Skeleton of a polygon, Delaunay triangulation, Euclidean minimum spanning tree 1. Introduction The classical approach of computational geometry is the search for algorithms having the best possible worst case complexity. Unfortunately, for difficult problems, the algorithms become fairly complicated and the use of sophisticated data structures yields unpractical algorithms. Furthermore, the authors generally study only the order of magnitude of the complexity bu...