Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-443-94

Authors:

Date:

January 24, 1994

Pages:

25

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 anO(n2logn)

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, edited by Brown

Geometry, 1994 in Video Review

and Hershberger.