Point in Polygon
Problem Description
A polygon is a twodimensional geometric figure that has a finite number of sides. The sides of a polygon are made of straight line segments connected to each other end to end. The line segments of a polygon are called sides or edges. The point where two line segments meet is called vertex or corners, henceforth an angle is formed. An example of a polygon is a triangle with three sides.
A circle is also a plane figure but it is not considered as a polygon, because it is a curved shape and does not have sides or angles. Therefore, we can say, all the polygons are 2d shapes but not all the twodimensional figures are polygons.
The problem deals with identifying if a point lies inside a polygon or not.
Bounds Chart
Step Chart
Improvement Table
Complexity Classes  Algorithm Paper Links  Lower Bounds Paper Links 

Exp/Factorial  
Polynomial > 3  
Cubic  
Quadratic  
nlogn  [Swath Method (1978)]  
Linear  [Ray casting algorithm Shimrat; M (1962)]
[Nordbeck and Rystedt (1967)] [Sum of area (1962)] [Wedge (1985)] [Sign of offset (1987)] [Intersection sum of angle (1985)] [Orientation (1962)] 

logn 