Cutting triangular cycles of lines in space

Boris Aronov; Vladlen Koltun; Micha Sharir

Cutting triangular cycles of lines in space

Boris Aronov, Vladlen Koltun, Micha Sharir

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The cutting triangular cycles of lines in space were investigated. It was shown that a collection of lines in 3-space can be cut into a subquadratic number of pieces, such that all depth cycles defined by triples of lines are eliminated. A long-standing open problem in computational geometry, motivated by hidden-surface removal in computer graphics, was solved.

Original language	English (US)
Title of host publication	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
Pages	547-555
Number of pages	9
State	Published - 2003
Event	35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 9 2003 → Jun 11 2003

Other

Other	35th Annual ACM Symposium on Theory of Computing
Country/Territory	United States
City	San Diego, CA
Period	6/9/03 → 6/11/03

Keywords

Cycles
Hidden-surface removal
Lines in space
Weavings

ASJC Scopus subject areas

Software

Cite this

@inproceedings{cb3db2c062af447385262a02221b7b5c,

title = "Cutting triangular cycles of lines in space",

abstract = "The cutting triangular cycles of lines in space were investigated. It was shown that a collection of lines in 3-space can be cut into a subquadratic number of pieces, such that all depth cycles defined by triples of lines are eliminated. A long-standing open problem in computational geometry, motivated by hidden-surface removal in computer graphics, was solved.",

keywords = "Cycles, Hidden-surface removal, Lines in space, Weavings",

author = "Boris Aronov and Vladlen Koltun and Micha Sharir",

year = "2003",

language = "English (US)",

pages = "547--555",

booktitle = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

note = "35th Annual ACM Symposium on Theory of Computing ; Conference date: 09-06-2003 Through 11-06-2003",

}

TY - GEN

T1 - Cutting triangular cycles of lines in space

AU - Aronov, Boris

AU - Koltun, Vladlen

AU - Sharir, Micha

PY - 2003

Y1 - 2003

N2 - The cutting triangular cycles of lines in space were investigated. It was shown that a collection of lines in 3-space can be cut into a subquadratic number of pieces, such that all depth cycles defined by triples of lines are eliminated. A long-standing open problem in computational geometry, motivated by hidden-surface removal in computer graphics, was solved.

AB - The cutting triangular cycles of lines in space were investigated. It was shown that a collection of lines in 3-space can be cut into a subquadratic number of pieces, such that all depth cycles defined by triples of lines are eliminated. A long-standing open problem in computational geometry, motivated by hidden-surface removal in computer graphics, was solved.

KW - Cycles

KW - Hidden-surface removal

KW - Lines in space

KW - Weavings

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

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

M3 - Conference contribution

AN - SCOPUS:0038784528

SP - 547

EP - 555

BT - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 35th Annual ACM Symposium on Theory of Computing

Y2 - 9 June 2003 through 11 June 2003

ER -

Cutting triangular cycles of lines in space

Abstract

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this