Does a point lie inside a polygon ? (Q1824391): Difference between revisions

The algorithmic question raised in the title is a special case of the so- called planar point location problem that belongs to the fundamental and well-studied problems in Computational Geometry. Of the various results known, three simple approaches are reviewed: two linear algorithms that work for arbitrary planar polygons, and an algorithm of logarithmic worst-case run time for star-shaped polygons. The author proceeds by proposing a new algorithm that works for convex polygons only but needs linear run time in the worst case. Optimal solutions to the point location problem can be found in \textit{H. Edelsbrunner}, \textit{L. J. Guibas}, and \textit{J. Stolfi} [SIAM J. Comput. 15, 317-340 (1986; Zbl 0602.68102)], \textit{D. G. Kirkpatrick} [SIAM J. Comput. 12, 28-35 (1983; Zbl 0501.68034)] \textit{N. Sarnak} and \textit{R. E. Tarjan} [Commun. ACM 29, No.7, 669-679 (1986)].