Back to Search Start Over

Computing the convex hull of disks using only their chirotope

Authors :
Habert, Luc
Pocchiola, Michel
Source :
idUS. Depósito de Investigación de la Universidad de Sevilla, instname
Publication Year :
2004

Abstract

We show that the convex hull of a collection of n pairwise disjoint disks in the plane is computable in O(n log n) time using only the chirotope of the collection of disks. The method relies mainly on the development of an (elementary) theory of convexity in the universal covering space of the punctured plane.

Details

Database :
OpenAIRE
Journal :
idUS. Depósito de Investigación de la Universidad de Sevilla, instname
Accession number :
edsair.dedup.wf.001..4283986677cc7631036c806b64e68ae8