Efficient and small representation of line arrangements with applications

D. P. Dobkin, A. Tal

Research output: Contribution to conferencePaper

6 Scopus citations

Abstract

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)
Pages293-301
Number of pages9
DOIs
StatePublished - Jan 1 2001
Event17th Annual Symposium on Computational Geometry (SCG'01) - Medford, MA, United States
Duration: Jun 3 2001Jun 5 2001

Other

Other17th Annual Symposium on Computational Geometry (SCG'01)
CountryUnited States
CityMedford, MA
Period6/3/016/5/01

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

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

  • Cite this

    Dobkin, D. P., & Tal, A. (2001). Efficient and small representation of line arrangements with applications. 293-301. Paper presented at 17th Annual Symposium on Computational Geometry (SCG'01), Medford, MA, United States. https://doi.org/10.1145/378583.378707