Vertical decomposition for point locations, part 2: randomized incremental construction

Point location is the problem of determining the face of a subdivision that 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 show how to construct the vertical decomposition together with a search structure using a randomized incremental construction. This is the 2nd out of 3 videos about the vertical decomposition. I give the analysis of the randomized incremental construction in the third video. see https://www.win.tue.nl/~kbuchin/teaching/2IMA15/slides/04-pointlocation.pdf for slides. 00:00 Setup 02:05 Nodes of the search structure 03:40 Example 07:21 Point location 08:41 Updating the vertical decomposition 10:59 Updating the search structure 13:51 Observations 17:02 Why randomization? 18:06 Worst-case depth of the search structure 19:54 Worst-case size of the search structure