On measuring areas of polygons.
Jurek Czyzowicz, F. Contreras-Alcalá, Jorge Urrutia · 1998
The measurement of areas and volumes of sets is a fundamental problem in mathematics and Computational Geometry. It is generally accepted that one of the motivations that fueled the development of geometry in early civilizations was the need to measure land for taxation purposes [1]. It is straightforward to see that calculating areas of polygons in the plane, and that volumes of polyherdra in R3 can be done in linear time. In this paper we study the following problem: Suppose that we split a simple polygon P into two subpolygons Q1 and Q2 by cutting it along a line segment joining two mutually visible points p and q on its boundary, see Figure 1. How quickly can we measure the areas of Q and R? It is easy to see that this problem can be solved optimally in linear time. Our main objective here, is to study how to speed up the measurement of the areas of Q1 and Q2 by using some preprocessing. We prove that after a linear amount of preprocessing the problems listed beQ 2 Q 1 p