Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas

Abstract : The existing O(n log n) algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental algorithms for these problems is that the introduction of a new circle or parabola can cause Theta(n) structural changes, leading to Theta(n^2) total structural changes during the running of the algorithm. In this note we examine the geometry of these problems and show that, if the circles or parabolas are first sorted by appropriate parameters before constructing the convex hull or lower envelope incrementally, then each new addition may cause at most 3 changes in an amortized sense. These observations are then used to develop O(n log n) incremental algorithms for these problems.
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 1995, 56 (3), pp.157-164. 〈10.1016/0020-0190(95)00132-V〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00413163
Contributeur : Olivier Devillers <>
Soumis le : jeudi 3 septembre 2009 - 13:16:40
Dernière modification le : mercredi 7 mars 2018 - 10:45:23
Document(s) archivé(s) le : mardi 15 juin 2010 - 23:08:00

Fichier

dg-iafch-95.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Olivier Devillers, Mordecai Golin. Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas. Information Processing Letters, Elsevier, 1995, 56 (3), pp.157-164. 〈10.1016/0020-0190(95)00132-V〉. 〈inria-00413163〉

Partager

Métriques

Consultations de la notice

486

Téléchargements de fichiers

171