# Analytical Solution for the Problem of Point Location in Arbitrary Planar Domains
## 2 Related Work  
The first known reference to an algorithm for the point location problem dates back to 1962 by [PERSON] [2]. That early algorithm had some limitations pointed out soon after by [PERSON] [3], and later by [PERSON], who also states to have delivered, in 1970, a code written in FORTRAN for this same problem [4]. The books by [PERSON] and [PERSON], published in 1985 [5], and by [PERSON], published in 1990 [6], also covered the point in the polygon problem and have been useful references for many other authors and programmers who have developed specific implementations with adaptations for their own set-ups. Still, nowadays, it is easy to find papers in conferences and journals--in very diverse contexts--where this problem is addressed, even if the novelties have stabilized a long time ago around the two main principles, as described further below.  
Eventually, what has become one of the most well-known references in the literature was the publication _Point in Polygon Strategies_, in 1994, by [PERSON] [7], and also some years later, the work of [PERSON] and [PERSON], in 2001 [8], which is the algorithm being used in Matlab for point location in arbitrary polygons.  
A clarification is recommended here to better focus the scope of the paper. Actually, there are two kinds of challenges in this problem: the \"point in region\" problem, and the \"point location in subdivisions of the plane\". Although related, there are some formal differences in these problems.  
In the first problem, there is only one region, and we are testing whether a point lies inside or outside of it. In the second problem, there is a group of regions (typically a subdivision of the plane), and we need to identify which specific region the point belongs to. The first problem is to be solved using containment tests specific to the region (e.g., point-in-polygon), and it has constant-time complexity relative to the number of regions but may depend on the complexity of the region's boundary. The second problem typically involves building a data structure for efficient spatial querying across many regions, with logarithmic or sublinear complexity relative to the number of regions in the subdivision. The second problem usually involves triangulated regions (using Delaunay triangulation), and several works stand out in that front, ranging from the fundamentals from Voronoi diagrams [9] and Delaunay triangulation, including later optimizations for better data structure management [10], up to actual point location algorithms in such triangular subdivisions of the plane [11; 12].  
This paper focuses specifically on the first problem and proposes an alternative solution by including additionally the ability to extend the regions to general curve-shaped boundaries. So, in this paper, the expression \"point location\" refers to assessing whether some point lies inside or outside a given planar region.  
Figure 1: Examples of shapes bounded by linear, circular, or Bézier segments, including twisting and self-intersection, and for which lacks a procedure to determine with the same algorithmic process the relative location of the points illustrated. The case on the right is much more complex than the one on the left, and that can be challenging, even for humans.