Lines avoiding unit balls in three dimensions

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

doi:10.1007/s00454-005-1166-2

Lines avoiding unit balls in three dimensions

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

Research output: Contribution to journal › Article › peer-review

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)
Pages (from-to)	231-250
Number of pages	20
Journal	Discrete and Computational Geometry
Volume	34
Issue number	2
DOIs	https://doi.org/10.1007/s00454-005-1166-2
State	Published - Aug 2005

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-005-1166-2

Cite this

@article{49b965f300064e6e8d0ef52379da2db2,

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

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

year = "2005",

month = aug,

doi = "10.1007/s00454-005-1166-2",

language = "English (US)",

volume = "34",

pages = "231--250",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Lines avoiding unit balls in three dimensions

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Koltun, Vladlen

AU - Sharir, Micha

PY - 2005/8

Y1 - 2005/8

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.

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

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

U2 - 10.1007/s00454-005-1166-2

DO - 10.1007/s00454-005-1166-2

M3 - Article

AN - SCOPUS:23944451604

SN - 0179-5376

VL - 34

SP - 231

EP - 250

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -

Lines avoiding unit balls in three dimensions

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this