Lines in space - combinatorics, algorithms and applications

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

Lines in space - combinatorics, algorithms and applications

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

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

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 language	English (US)
Title of host publication	Proc Twenty First Annu ACM Symp Theory Comput
Publisher	Publ by ACM
Pages	382-393
Number of pages	12
ISBN (Print)	0897913078
State	Published - 1989
Event	Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing - Seattle, WA, USA Duration: May 15 1989 → May 17 1989

Publication series

Name	Proc Twenty First Annu ACM Symp Theory Comput

Other

Other	Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing
City	Seattle, WA, USA
Period	5/15/89 → 5/17/89

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@inproceedings{b21e2cb025bf42f68102c17a7a91212f,

title = "Lines in space - combinatorics, algorithms and applications",

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

author = "Bernard Chazelle and Herbert Edelsbrunner and Guibas, {Leonidas J.} and Micha Sharir",

year = "1989",

language = "English (US)",

isbn = "0897913078",

series = "Proc Twenty First Annu ACM Symp Theory Comput",

publisher = "Publ by ACM",

pages = "382--393",

booktitle = "Proc Twenty First Annu ACM Symp Theory Comput",

note = "Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing ; Conference date: 15-05-1989 Through 17-05-1989",

}

TY - GEN

T1 - Lines in space - combinatorics, algorithms and applications

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

AU - Guibas, Leonidas J.

AU - Sharir, Micha

PY - 1989

Y1 - 1989

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:0024860012

SN - 0897913078

T3 - Proc Twenty First Annu ACM Symp Theory Comput

SP - 382

EP - 393

BT - Proc Twenty First Annu ACM Symp Theory Comput

PB - Publ by ACM

T2 - Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing

Y2 - 15 May 1989 through 17 May 1989

ER -

Lines in space - combinatorics, algorithms and applications

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this