The number of lines tangent to arbitrary convex polyhedra in 3D

H. Brönnimann; O. Devillers; V. Dujmović; H. Everett; M. Glisse; X. Goaoc; S. Lazard; H. S. Na; S. Whitesides

doi:10.1145/997817.997827

The number of lines tangent to arbitrary convex polyhedra in 3D

H. Brönnimann
, O. Devillers
, V. Dujmović
, H. Everett
, M. Glisse
, X. Goaoc
, S. Lazard
, H. S. Na
, S. Whitesides

École Polytechnique

Polytechnic University
INRIA
McGill University
INRIA Institut National de Recherche en Informatique et en Automatique
Soongsil University

Research output: Contribution to conference › Paper › peer-review

2 Citations (Scopus)

Abstract

We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝR³ with n edges in total form θ(n ²) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of κ convex polyhedra with a total of n edges admits, in the worst case, θ(n ²κ²) connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n²κ²) on the number of non-occluded maximal line segments tangent to any four of these κ convex polyhedra.

Original language	English
Pages	46-55
Number of pages	10
DOIs	https://doi.org/10.1145/997817.997827
Publication status	Published - 1 Jan 2004
Event	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: 9 Jun 2004 → 11 Jun 2004

Conference

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

Keywords

3D visibility
Computational geometry
Visibility complex
Visual events

Access to Document

10.1145/997817.997827

Cite this

Brönnimann, H., Devillers, O., Dujmović, V., Everett, H., Glisse, M., Goaoc, X., Lazard, S., Na, H. S., & Whitesides, S. (2004). The number of lines tangent to arbitrary convex polyhedra in 3D. 46-55. Paper presented at Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04), Brooklyn, NY, United States. https://doi.org/10.1145/997817.997827

@conference{8efac536fc0f4566a05f3728e8b3289f,

title = "The number of lines tangent to arbitrary convex polyhedra in 3D",

abstract = "We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝR3 with n edges in total form θ(n 2) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of κ convex polyhedra with a total of n edges admits, in the worst case, θ(n 2κ2) connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n2κ2) on the number of non-occluded maximal line segments tangent to any four of these κ convex polyhedra.",

keywords = "3D visibility, Computational geometry, Visibility complex, Visual events",

author = "H. Br{\"o}nnimann and O. Devillers and V. Dujmovi{\'c} and H. Everett and M. Glisse and X. Goaoc and S. Lazard and Na, \{H. S.\} and S. Whitesides",

year = "2004",

month = jan,

day = "1",

doi = "10.1145/997817.997827",

language = "English",

pages = "46--55",

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

}

Brönnimann, H, Devillers, O, Dujmović, V, Everett, H, Glisse, M, Goaoc, X, Lazard, S, Na, HS & Whitesides, S 2004, 'The number of lines tangent to arbitrary convex polyhedra in 3D', Paper presented at Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04), Brooklyn, NY, United States, 9/06/04 - 11/06/04 pp. 46-55. https://doi.org/10.1145/997817.997827

TY - CONF

T1 - The number of lines tangent to arbitrary convex polyhedra in 3D

AU - Brönnimann, H.

AU - Devillers, O.

AU - Dujmović, V.

AU - Everett, H.

AU - Glisse, M.

AU - Goaoc, X.

AU - Lazard, S.

AU - Na, H. S.

AU - Whitesides, S.

PY - 2004/1/1

Y1 - 2004/1/1

N2 - We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝR3 with n edges in total form θ(n 2) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of κ convex polyhedra with a total of n edges admits, in the worst case, θ(n 2κ2) connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n2κ2) on the number of non-occluded maximal line segments tangent to any four of these κ convex polyhedra.

AB - We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝR3 with n edges in total form θ(n 2) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of κ convex polyhedra with a total of n edges admits, in the worst case, θ(n 2κ2) connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n2κ2) on the number of non-occluded maximal line segments tangent to any four of these κ convex polyhedra.

KW - 3D visibility

KW - Computational geometry

KW - Visibility complex

KW - Visual events

U2 - 10.1145/997817.997827

DO - 10.1145/997817.997827

M3 - Paper

AN - SCOPUS:4544244073

SP - 46

EP - 55

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

Y2 - 9 June 2004 through 11 June 2004

ER -

The number of lines tangent to arbitrary convex polyhedra in 3D

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this