Computing half-plane and strip discrepancy of planar point sets

DOI10.1016/0925-7721(95)00010-0MaRDI QIDQ1917044zbMATH OpenOpenAlexFDO

Authors Mark de Berg

Publication date 14 July 1996

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/17087

zbMATH Keywords

computer graphicshalf-plane discrepancy

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Tight upper bounds for the discrepancy of half-spaces
• Calculation of the discrepancy of a finite set of points in the unit n -cube
• Tighter bounds for the discrepancy of boxes and polytopes
• Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension

Cites work

• Constructing Arrangements of Lines and Hyperplanes with Applications
• Finding the upper envelope of n line segments in O(n log n) time
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 464639 (Why is no real title available?)
• scientific article; zbMATH DE number 4000052 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences

Cited in

(1)

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

This page was built for publication: Computing half-plane and strip discrepancy of planar point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1917044)