Lines avoiding balls in three dimensions revisited

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

Let B be a collection of n arbitrary balls in ℝ 3. We establish an almost-tight upper bound of O(n 3+ε), for any ε>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+ε) free isolated tangents, for any ε>0. This generalizes the result of Agarwal et al. (Discrete Comput. Geom. 34:231-250, 2005), 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 Ω(n 3) of Glisse and Lazard (Proc. 26th Annu. Symp. Comput. Geom., pp. 48-57, 2010). Our approach is constructive and yields an algorithm that computes the discrete representation of the boundary of F(B) in O(n 3+ε) time, for any ε>0.

שפה מקוריתאנגלית אמריקאית
עמודים (מ-עד)65-93
מספר עמודים29
כתב עתDiscrete and Computational Geometry
כרך48
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יולי 2012
פורסם באופן חיצוניכן

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.2600.2608???
  • ???subjectarea.asjc.2600.2607???
  • ???subjectarea.asjc.1700.1703???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Lines avoiding balls in three dimensions revisited'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי