Efficient and small representation of line arrangements with applications

D. P. Dobkin; A. Tal

doi:10.1145/378583.378707

Efficient and small representation of line arrangements with applications

D. P. Dobkin, A. Tal

Research output: Contribution to conference › Paper › peer-review

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 language	English (US)
Pages	293-301
Number of pages	9
DOIs	https://doi.org/10.1145/378583.378707
State	Published - 2001
Event	17th Annual Symposium on Computational Geometry (SCG'01) - Medford, MA, United States Duration: Jun 3 2001 → Jun 5 2001

Other

Other	17th Annual Symposium on Computational Geometry (SCG'01)
Country/Territory	United States
City	Medford, MA
Period	6/3/01 → 6/5/01

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/378583.378707

Cite this

@conference{c9eed66584574e3b8d1e41988c6c0720,

title = "Efficient and small representation of line arrangements with applications",

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

author = "Dobkin, {D. P.} and A. Tal",

year = "2001",

doi = "10.1145/378583.378707",

language = "English (US)",

pages = "293--301",

note = "17th Annual Symposium on Computational Geometry (SCG'01) ; Conference date: 03-06-2001 Through 05-06-2001",

}

TY - CONF

T1 - Efficient and small representation of line arrangements with applications

AU - Dobkin, D. P.

AU - Tal, A.

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0034825858&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034825858&partnerID=8YFLogxK

U2 - 10.1145/378583.378707

DO - 10.1145/378583.378707

M3 - Paper

AN - SCOPUS:0034825858

SP - 293

EP - 301

T2 - 17th Annual Symposium on Computational Geometry (SCG'01)

Y2 - 3 June 2001 through 5 June 2001

ER -

Efficient and small representation of line arrangements with applications

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this