On Point-inclusion Test in Convex Polygons and Polyhedrons

Document Type : Research Paper

Authors

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

2 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