Lines in space - combinatorics, algorithms and applications

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations

Abstract

We study combinatorial and algorithmic problems involving arrangements of n lines in 3-dimensional space, and then present applications of our results to a variety of problems on polyhedral terrains. The tools used to obtain the results include Pluecker coordinates for lines in space, random sampling in geometric problems, and a new variant of segment trees.

Original languageEnglish (US)
Title of host publicationProc Twenty First Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages382-393
Number of pages12
ISBN (Print)0897913078
StatePublished - Dec 1 1989
EventProceedings of the Twenty First Annual ACM Symposium on Theory of Computing - Seattle, WA, USA
Duration: May 15 1989May 17 1989

Other

OtherProceedings of the Twenty First Annual ACM Symposium on Theory of Computing
CitySeattle, WA, USA
Period5/15/895/17/89

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Lines in space - combinatorics, algorithms and applications'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., Edelsbrunner, H., Guibas, L. J., & Sharir, M. (1989). Lines in space - combinatorics, algorithms and applications. In Proc Twenty First Annu ACM Symp Theory Comput (pp. 382-393). Publ by ACM.