On lines avoiding unit balls in three dimensions

Pankaj K. Agarwal; Boris Aronov; Vladlen Koltun; Micha Sharir

On lines avoiding unit balls in three dimensions

Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, Micha Sharir

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

Abstract

Let B be a set of n unit balls in ℝ³. We show that the combinatorial complexity of the space of lines in ℝ³ that avoid all the balls of B is O(n^3+ε), for any ε > 0. This result has connections to problems in visibility, ray shooting, motion planning and geometric optimization.

Original language	English (US)
Title of host publication	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Pages	36-45
Number of pages	10
State	Published - 2004
Event	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004

Other

Other	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Country/Territory	United States
City	Brooklyn, NY
Period	6/9/04 → 6/11/04

Keywords

Combinatorial complexity
Lines in space
Visibility

ASJC Scopus subject areas

Software
Geometry and Topology
Safety, Risk, Reliability and Quality
Chemical Health and Safety

Cite this

@inproceedings{026908696c254c51a785dc64aab54537,

title = "On lines avoiding unit balls in three dimensions",

abstract = "Let B be a set of n unit balls in ℝ3. We show that the combinatorial complexity of the space of lines in ℝ3 that avoid all the balls of B is O(n3+ε), for any ε > 0. This result has connections to problems in visibility, ray shooting, motion planning and geometric optimization.",

keywords = "Combinatorial complexity, Lines in space, Visibility",

author = "Agarwal, {Pankaj K.} and Boris Aronov and Vladlen Koltun and Micha Sharir",

year = "2004",

language = "English (US)",

pages = "36--45",

booktitle = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)",

note = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) ; Conference date: 09-06-2004 Through 11-06-2004",

}

TY - GEN

T1 - On lines avoiding unit balls in three dimensions

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Koltun, Vladlen

AU - Sharir, Micha

PY - 2004

Y1 - 2004

N2 - Let B be a set of n unit balls in ℝ3. We show that the combinatorial complexity of the space of lines in ℝ3 that avoid all the balls of B is O(n3+ε), for any ε > 0. This result has connections to problems in visibility, ray shooting, motion planning and geometric optimization.

AB - Let B be a set of n unit balls in ℝ3. We show that the combinatorial complexity of the space of lines in ℝ3 that avoid all the balls of B is O(n3+ε), for any ε > 0. This result has connections to problems in visibility, ray shooting, motion planning and geometric optimization.

KW - Combinatorial complexity

KW - Lines in space

KW - Visibility

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

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

M3 - Conference contribution

AN - SCOPUS:4544360682

SP - 36

EP - 45

BT - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

T2 - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

Y2 - 9 June 2004 through 11 June 2004

ER -

On lines avoiding unit balls in three dimensions

Abstract

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this