A sublogarithmic convex hull algorithm
Authors:Per-Olof Fjällström, Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson
Published in:BIT 30,3 (1990), 378-384
DOI:10.1007/BF01931655
Copyright:© Springer
Abstract:We present a parallel algorithm for finding the convex hull of a sorted set of points in the plane. Our algorithm runs in O(log n / loglog n) time using O(n loglog n / log n) processors in the Common CRCW PRAM computational model, which is shown to be time and cost optimal. The algorithm is based on n1/3 divide-and-conquer and uses a simple pointer-based data structure.
BibLATEX:
@article{FKLP1990J,
  author = {Per-Olof Fj\"{a}llstr\"{o}m and Jyrki Katajainen and Christos
    Levcopoulos and Ola Petersson},
  title = {A sublogarithmic convex hull algorithm},
  journaltitle = {BIT},
  volume = {30},
  number = {3},
  year = {1990},
  pages = {378--384},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.