A 1 log N parallel algorithm for detecting convex hulls on image boards

J C Lin; J Y Lin

doi:10.1109/83.679445

A 1 log N parallel algorithm for detecting convex hulls on image boards

IEEE Trans Image Process. 1998;7(6):922-5. doi: 10.1109/83.679445.

Authors

J C Lin¹, J Y Lin

Affiliation

¹ Department of Computer and Information Science, National Chiao Tung University, Hsinchu 300, Taiwan, ROC. jclin@cis.nctu.edu.tw

PMID: 18276309
DOI: 10.1109/83.679445

Abstract

By finding the maximum and minimum of {yi-mxi|1=or<i=or<N} for certain slopes m, we propose here a simple and fast parallel algorithm to obtain the convex hull of N arbitrarily given points on an image board, The mathematical theory needed is included, and computation time is 1 log N.