A priori filtration of points for finding convex hull

Abstract

Convex hull is the minimum area convex polygon containing the planar set. By now there are quite many convex hull algorithms (Graham Scan, Jarvis March, QuickHull, Incremental, Divide‐and‐Conquer, Marriage‐before‐Conquest, Monotone Chain, Brute Force). The main attention while choosing the algorithm is paid to the running time. In order to raise the efficiency of all the algorithms an idea of a priori filtration of points is given in this article. Besides, two new algorithms have been created and presented. The experiment research has shown a very good efficiency of these algorithms.

Apriorinis taškų filtravimas, ieškant iškilojo apvalkalo

Santrauka. Plokštumos taškų iškilasis apvalkalas yra mažiausias galimas iškilasis daugiakampis, kai visi aibės taškai yra jo viduje arba ant briaunų bei viršūnių. Jau šiuo metu literatūroje aptinkama nemažai skaičius iškilojo apvalkalo radimo algoritmų (Graham Scan, Jarvis March, QuickHull, Incremental, Divide-and-Conquer, Marriage-before-Conquest, Monotone Chain, Brute Force). Renkantis algoritmą, daugiausia dėmesio skiriama algoritmo atlikimo spartai. Straipsnyje pasiūlyta, kokių veiksmų imtis, siekiant padidinti algoritmų spartą. Šiomis idėjomis remiantis, sukurti du nauji algoritmai, pasižymintys labai dideliu efektyvumu.

Reikšminiai žodžiai: iškilasis apvalkalas, apriorinis taškų filtravimas, efektyvumas, Graham Scan, Jarvis March, QuickHull.

First Published Online: 21 Oct 2010