On computing the closest boundary point on the convex hull

Abstract

We observe a somewhat surprising result: Given a set S of n points in E2 and a point q∉S, ⊖(n) time is sufficient to determine a point on the convex hull, CH(S), that is nearest to q when q is exterior to CH(S). However, if q lies in the interior of CH(S), then ⊖(n log n) time is both necessary and sufficient to determine such a point. We also observe that ⊖(n) time suffices to determine whether or not the point q lies inside CH(S). © 1989.