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

Résultats de recherche: Contribution à une conférence › Papier › Revue par des pairs

2 Citations (Scopus)

Résumé

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.

langue originale	Anglais
Pages	46-55
Nombre de pages	10
Les DOIs	https://doi.org/10.1145/997817.997827
état	Publié - 1 janv. 2004
Evénement	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, États-Unis Durée: 9 juin 2004 → 11 juin 2004

Une conférence

Une conférence	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Pays/Territoire	États-Unis
La ville	Brooklyn, NY
période	9/06/04 → 11/06/04

Accès au document

10.1145/997817.997827

Contient cette citation

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. Papier présenté � Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04), Brooklyn, NY, États-Unis. 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', Papier présenté � Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04), Brooklyn, NY, États-Unis, 9/06/04 - 11/06/04 p. 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

Résumé

Une conférence

Accès au document

Empreinte digitale

Contient cette citation