Vertical decomposition for point locations, part 1: the data structure

Point location is the problem of determining the face of a subdivision which contains a query point. The vertical decomposition is a data structure of linear size that facilitates point location queries in O(log n) time. Here I introduce the point location problem, show as first (simpler but less efficient) solution the slab decomposition, and from there derive the vertical decomposition. Finally, I discuss how to store it. This is the first out of 3 videos about the vertical decomposition. In the other two, I give an algorithm to construct the vertical decomposition and analyze the algorithm. 00:00 Motivation: Point location 02:34 The point location problem 05:02 Point location in 1d 07:07 Slab decomposition 14:02 Vertical decomposition 19:48 Data Structure: Vertical Decomposition 22:29 Complexity of the Vertical Decomposition 25:34 From a planar subdivision to line segments