Point Location with Slab Decomposition

Sun, 04/11/2012 - 10:30

Point Location is a fundamental problem in Computational Geometry. Given a partition of the Euclidean space into disjoint areas, the problem faces the question: "In which area lies a given point?". This problem also reflects to world of data structure, because of the need to create a suitable structure that will keep the data and allow answering the question efficiently for any given point. We will introduce a method called Slab Decomposition which solves the problem in a simple and efficient way by using advanced search trees, called Persistent.  Moreover, we have programmed this method and approved it to be useful.