A Fast Algorithm to Decide the Inclusion of a Point in the Convex Hull of a Two-Dimensional Point Set

Abstract

This paper presents a new fast algorithm to compute the twodimensional inclusion test of a point in the convex hull of a set of points, without computing the convex hull. The algorithm is based on the classification of the points in octants of the plane. This classification step for each point requires only simple test operations, and makes the algorithm run in at worst, O(ns). For point sets larger than 11 points, the proposed algorithm is faster than other known approaches. The paper includes a practical evaluation of the algorithm, comparing it with several previously known approaches.