Synergistic solutions for merging and computing planar convex hulls
Author
dc.contributor.author
Barbay, Jérémy
Author
dc.contributor.author
Ochoa, Carlos
Admission date
dc.date.accessioned
2019-05-31T15:20:00Z
Available date
dc.date.available
2019-05-31T15:20:00Z
Publication date
dc.date.issued
2018
Cita de ítem
dc.identifier.citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volumen 10976 LNCS, 2018, Pages 156-167
Identifier
dc.identifier.issn
16113349
Identifier
dc.identifier.issn
03029743
Identifier
dc.identifier.other
10.1007/978-3-319-94776-1_14
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/169418
Abstract
dc.description.abstract
We describe and analyze the first adaptive algorithm for merging k convex hulls in the plane. This merging algorithm in turn yields a synergistic algorithm to compute the convex hull of a set of planar points, taking advantage both of the positions of the points and their order in the input. This synergistic algorithm asymptotically outperforms all previous solutions for computing the convex hull in the plane.