Name
Abstract | ||
|---|---|---|
Let B be a collection of n arbitrary balls in R(3). We establish an almost-tight upper bound of O(n(3+epsilon)), for any epsilon > 0, on the complexity of the space F(B) of all the lines that avoid all the members of B. In particular, we prove that the balls of B admit O(n(3+epsilon)) free isolated tangents, for any epsilon > 0. This generalizes the result of Agarwal et al. [1], who established this bound only for congruent balls, and solves an open problem posed in that paper. Our bound almost meets the recent lower bound of Omega(n(3)) of Glisse and Lazard [6].Our approach is constructive and yields an algorithm that computes a discrete representation of the boundary of F(B) in O(n(3+epsilon)) time, for any epsilon > 0. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1810959.1810970 | PROCEEDINGS OF THE TWENTY-SIXTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'10) |
Keywords | DocType | Citations |
Free lines, lines in space, tangency surfaces, arrangements, combinatorial complexity | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Natan Rubin | 1 | 92 | 11.03 |