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--2019), 99 pp.
Full text:<pdf.gif>PDF (847 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.gif>HTML (Technical report)  <html.gif>HTML (Journal article)  <html.gif>HTML (tar archive)  
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--2019},
  pagetotal = {99},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 2019-02-22.