| Convex-hull algorithms in C++ | |
| Authors: | Ask Neve Gamby and Jyrki Katajainen |
| Publication: | CPH STL report 2018-1, Department of Computer Science, University of Copenhagen (2018–2020), 107 pp. |
| Full text: |  PDF (731 kB) |
| Abstract: | In the two-dimensional convex-hull problem we are given a multiset S
of points and the task is to find those points of S that are the
vertices of the smallest convex polygon enclosing all the points
of S. In the output the vertices must be reported in the order in
which they appear along the boundary of the polygon—either in clockwise
or counterclockwise order. Further, when the coordinates of the points
are integers, the computed output should always be correct. This collection contains our implementations of the following convex-hull algorithms: plane-sweep, torch, divide & conquer, quickhull, poles-first, throw-away, introhull, and bucketing. For an input of size n, none of our implementations use more than O(√n) extra words of memory and all run in linear expected time when the input points are randomly distributed. As far as we know, this collection contains the best known algorithms—both with respect to time and space usage. If you know a better algorithm—or a better implementation written in C++—and think that it should be in this collection, let us know. Keep in mind that we promise a reward of 2.56 brownie points for every person who is the first to report an error in one of the programs released in this collection. |
| Related: |  HTML (Technical report) HTML (Journal article) HTML (Conference paper)  ZIP (zip file) |
| BibLATEX: | @report{GK2018S,
author = {Ask Neve Gamby and Jyrki Katajainen},
title = {Convex-hull algorithms in {C}\texttt{++}},
type = {CPH STL report},
number = {2018-1},
institution = {Department of Computer Science, University of Copenhagen},
year = {2018--2020},
pagetotal = {107},
}
|