Document Type : Research Paper

Authors

• Mahdi Imanparast ¹
• Mehdi Kazemi Torbaghan ²

¹ Department of Computer Science, University of Bojnord, Bojnord, Iran

² Department of Mathematics, University of Bojnord

Abstract

A new algorithm for point-inclusion test in convex polygons is introduced. The proposed algorithm answers the point-inclusion test in convex polygons in $\mathcal{O}(\log n)$ time without any preprocessing and with $\mathcal{O}(n)$ space. The proposed algorithm is extended to do the point-inclusion test in convex polyhedrons in three dimensional space. This algorithm can solve the point-inclusion test in convex $3D$ polyhedrons in $\mathcal{O}(\log n)$ time with $\mathcal{O}(n)$ preprocessing time and $\mathcal{O}(n)$ space.

Keywords

• Point-in-polygon
• Point-inclusion test
• Convex polygons
• Convex polyhedrons
• Preprocessing time