Quick links

Computing the Rectangle Discrepancy

Report ID:
January 24, 1994
Download Formats:


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.
Follow us: Facebook Twitter Linkedin