Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning

David P. Dobkin; Dimitrios Gunopulos; Wolfgang Maass

doi:10.1006/jcss.1996.0034

Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning

David P. Dobkin
, Dimitrios Gunopulos
, Wolfgang Maass

Research output: Contribution to journal › Article › peer-review

44 Scopus citations

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.

Original language	English (US)
Pages (from-to)	453-470
Number of pages	18
Journal	Journal of Computer and System Sciences
Volume	52
Issue number	3
DOIs	https://doi.org/10.1006/jcss.1996.0034
State	Published - Jun 1996

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1006/jcss.1996.0034

Cite this

@article{9c51adf01159427984ff72688ca78c4d,

title = "Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning",

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.",

author = "Dobkin, \{David P.\} and Dimitrios Gunopulos and Wolfgang Maass",

note = "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.",

year = "1996",

month = jun,

doi = "10.1006/jcss.1996.0034",

language = "English (US)",

volume = "52",

pages = "453--470",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "3",

}

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 - https://www.scopus.com/pages/publications/0030169930

UR - https://www.scopus.com/pages/publications/0030169930#tab=citedBy

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 -

Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this