Efficient and small representation of line arrangements with applications

D. P. Dobkin, A. Tal

Research output: Contribution to conferencePaperpeer-review

6 Scopus citations


This paper addresses the problem of lossy compression of arrangements. Given an arrangement of n lines in the plane, we show how to construct another arrangement consisting of many fewer lines. We give theoretical and empirical bounds to demonstrate the tradeoffs between the size of the new arrangement and the error from lossiness. For the specific application of computing discrepancies of point sets, we demonstrate that speedups by factors of several hundred are possible while introducing small errors. This research has been enabled by various visualization techniques and is accompanied by a video.

Original languageEnglish (US)
Number of pages9
StatePublished - 2001
Event17th Annual Symposium on Computational Geometry (SCG'01) - Medford, MA, United States
Duration: Jun 3 2001Jun 5 2001


Other17th Annual Symposium on Computational Geometry (SCG'01)
Country/TerritoryUnited States
CityMedford, MA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Efficient and small representation of line arrangements with applications'. Together they form a unique fingerprint.

Cite this