Polygon Area Problems.
Ralph P. Boland, Jorge Urrutia · 2000
In this paper we study the problem of preprocessing a simple polygon so that, for any query chord of the polygon, the area of the subpolygons determined by the chord can be determined quickly. We give a solution to this problem requiring linear space and preprocessing time and constant query time. This is an improvement by a factor of O (log n) in space, preprocessing time, and query time over the best known algorithm. Furthermore our solution is simpler as well