Computing the Rectangle Discrepancy

Report ID: TR-443-94

---

Author: Gunopulos, Dimitrios / Dobkin, David P.

---

Date: 1994-01-24

---

Pages: 25

---

Download Formats: |Postscript|

---

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(n² 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.