NeuroCOLT: Neural Networks and Computational Learning Theory

NeuroCOLT

Neural Networks and Computational Learning Theory

1994	1995
1996	1997
1998	1999
2000	2001

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-95-008

Computing the Maximum Bichromatic Discrepancy, with applications to Computer Graphics and Machine Learning

David P. Dobkin
Princeton University

Dimitrios Gunopulos
Princeton University

Wolfgang Maass
Technische Universitaet Graz

Abstract
Computing the maximum bichromatic discrepancy is an interesting theoretical problem with important applications in computational learning theory, computational geometry and computer graphics. In this paper we give algorithms to compute the maximum bichromatic discrepancy for simple geometric ranges, including rectangles and halfspaces. In addition, we give extensions to other discrepancy problems.

Download Compressed Postscript