TY - JOUR
T1 - Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning
AU - Dobkin, David P.
AU - Gunopulos, Dimitrios
AU - Maass, Wolfgang
N1 - Funding Information:
* The research work of these authors was supported by NSF Grant CCR93-01254 and the Geometry Center. -E-mail address: dpd cs.princeton.edu. E-mail address: dg cs.princeton.edu. 9E-mail address: maass igi.tu-graz.ac.at.
PY - 1996/6
Y1 - 1996/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0030169930&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0030169930&partnerID=8YFLogxK
U2 - 10.1006/jcss.1996.0034
DO - 10.1006/jcss.1996.0034
M3 - Article
AN - SCOPUS:0030169930
SN - 0022-0000
VL - 52
SP - 453
EP - 470
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 3
ER -