# Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas

1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Keywords :
Type de document :
Rapport
[Research Report] RR-2280, INRIA. 1994
Domaine :

https://hal.inria.fr/inria-00074391
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:12:34
Dernière modification le : jeudi 11 janvier 2018 - 16:23:55
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:16:38

### Identifiants

• HAL Id : inria-00074391, version 1

### Citation

Olivier Devillers, Mordecai Golin. Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas. [Research Report] RR-2280, INRIA. 1994. 〈inria-00074391〉

### Métriques

Consultations de la notice

## 191

Téléchargements de fichiers