Insertion of a convex polygon in trapezoidal map and finding point location

Abstract

Point Location Problem is a part of Computational Geometry and it is used to determine the area that contains query point ‘q’. The main subject of my thesis was to describe and implement the algorithm that is used to insert convex polygon in map and analyze it’s run time. So ,we have proposed algorithms to perform new operations on an arrangement of line segments in the plane, represented by a trapezoidal map; the dynamic insertion of the convex polygon in the trapezoidal map, and then finding the top polygon, bottom polygon, left polygon and right polygon for a given query point in the map.