Computing the Rectangle Discrepancy

Abstract:

Computing the discrepancy is an interesting theoretical problem with
practical applications in computer graphics. We extend previous work
on discrepancy to a more useful model. We give an
O(n2 log n)
algorithm for computing the unanchored rectangle discrepancy of planar
point sets. In addition, we give extensions to other interesting
discrepancy problems.

This technical report has been published as

Computing the Rectangle Discrepancy. David P. Dobkin and
Dimitrios Gunopulos, Symposium on Computational
Geometry, 1994 in Video Review, edited by Brown
and Hershberger.