InforLorV4, PascalFrancis, Corpus, bibRecord, 000317

LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA

Identifieur interne : 000317 ( PascalFrancis/Corpus ); précédent : 000316; suivant : 000318

LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA

Auteurs : Hervé Brönnimann ; Olivier Devillers ; Vida Dujmovic ; Hazel Everett ; Marc Glisse ; Xavier Goaoc ; Sylvain Lazard ; Hyeon-Suk Na ; Sue Whitesides

Source :

SIAM journal on computing : (Print) [ 0097-5397 ] ; 2008.

RBID : Pascal:08-0208367

Descripteurs français

Pascal (Inist)
- Segment droite, Calcul 3 dimensions, Visibilité, Complexité, Construction, Polytope, Algorithme, Composante connexe, Pire cas, 52Bxx, 68Wxx, Transversal(graphe), Ensemble contour.

English descriptors

KwdEn :
- Algorithm, Complexity, Construction, Edge set, Line segment, Polytope, Three-dimensional calculations, Visibility.

Abstract

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in R³ with a total of n edges consists of Θ(n²) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, Θ(n²k²) connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an O(n²k² log n) time and O(nk²) space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0097-5397`
A03		`1`		`@0 SIAM j. comput. : (Print)`
A05				`@2 37`
A06				`@2 2`
A08	`01`	`1`	`ENG`	`@1 LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA`
A11	`01`	`1`		`@1 BRÖNNIMANN (Hervé)`
A11	`02`	`1`		`@1 DEVILLERS (Olivier)`
A11	`03`	`1`		`@1 DUJMOVIC (Vida)`
A11	`04`	`1`		`@1 EVERETT (Hazel)`
A11	`05`	`1`		`@1 GLISSE (Marc)`
A11	`06`	`1`		`@1 GOAOC (Xavier)`
A11	`07`	`1`		`@1 LAZARD (Sylvain)`
A11	`08`	`1`		`@1 NA (Hyeon-Suk)`
A11	`09`	`1`		`@1 WHITESIDES (Sue)`
A14	`01`			`@1 Polytechnic University @2 Brooklyn, NY 11201 @3 USA @Z 1 aut.`
A14	`02`			`@1 INRIA Sophia-Antipolis @2 Sophia-Antipolis @3 FRA @Z 2 aut.`
A14	`03`			`@1 School of Computer Science, Carleton University @2 Ottawa, ON @3 CAN @Z 3 aut.`
A14	`04`			`@1 LORIA-INRIA Lorraine, University Nancy 2 @2 Nancy @3 FRA @Z 4 aut. @Z 5 aut. @Z 6 aut. @Z 7 aut.`
A14	`05`			`@1 School of Computing, Soongsil University @2 Seoul @3 KOR @Z 8 aut.`
A14	`06`			`@1 School of Computer Science, McGill University @2 Montréal, QC @3 CAN @Z 9 aut.`
A20				`@1 522-551`
A21				`@1 2008`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 16063 @5 354000183013260090`
A44				`@0 0000 @1 © 2008 INIST-CNRS. All rights reserved.`
A45				`@0 25 ref.`
A47	`01`	`1`		`@0 08-0208367`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 SIAM journal on computing : (Print)`
A66	`01`			`@0 USA`
C01	`01`		`ENG`	@0 Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in R³ with a total of n edges consists of Θ(n²) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, Θ(n²k²) connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an O(n²k² log n) time and O(nk²) space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.
C02	`01`	`X`		`@0 001D02A08`
C02	`02`	`X`		`@0 001A02F02`
C02	`03`	`X`		`@0 001D02A05`
C03	`01`	`X`	`FRE`	`@0 Segment droite @5 17`
C03	`01`	`X`	`ENG`	`@0 Line segment @5 17`
C03	`01`	`X`	`SPA`	`@0 Segmento recta @5 17`
C03	`02`	`3`	`FRE`	`@0 Calcul 3 dimensions @5 18`
C03	`02`	`3`	`ENG`	`@0 Three-dimensional calculations @5 18`
C03	`03`	`X`	`FRE`	`@0 Visibilité @5 19`
C03	`03`	`X`	`ENG`	`@0 Visibility @5 19`
C03	`03`	`X`	`SPA`	`@0 Visibilidad @5 19`
C03	`04`	`X`	`FRE`	`@0 Complexité @5 20`
C03	`04`	`X`	`ENG`	`@0 Complexity @5 20`
C03	`04`	`X`	`SPA`	`@0 Complejidad @5 20`
C03	`05`	`X`	`FRE`	`@0 Construction @5 21`
C03	`05`	`X`	`ENG`	`@0 Construction @5 21`
C03	`05`	`X`	`SPA`	`@0 Construcción @5 21`
C03	`06`	`X`	`FRE`	`@0 Polytope @5 22`
C03	`06`	`X`	`ENG`	`@0 Polytope @5 22`
C03	`06`	`X`	`SPA`	`@0 Politope @5 22`
C03	`07`	`X`	`FRE`	`@0 Algorithme @5 23`
C03	`07`	`X`	`ENG`	`@0 Algorithm @5 23`
C03	`07`	`X`	`SPA`	`@0 Algoritmo @5 23`
C03	`08`	`X`	`FRE`	`@0 Composante connexe @4 INC @5 70`
C03	`09`	`X`	`FRE`	`@0 Pire cas @4 INC @5 71`
C03	`10`	`X`	`FRE`	`@0 52Bxx @4 INC @5 72`
C03	`11`	`X`	`FRE`	`@0 68Wxx @4 INC @5 73`
C03	`12`	`X`	`FRE`	`@0 Transversal(graphe) @4 INC @5 74`
C03	`13`	`X`	`FRE`	`@0 Ensemble contour @4 CD @5 96`
C03	`13`	`X`	`ENG`	`@0 Edge set @4 CD @5 96`
N21				`@1 133`
N44	`01`			`@1 OTO`
N82				`@1 OTO`

Format Inist (serveur)

NO :	PASCAL 08-0208367 INIST
ET :	LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA
AU :	BRÖNNIMANN (Hervé); DEVILLERS (Olivier); DUJMOVIC (Vida); EVERETT (Hazel); GLISSE (Marc); GOAOC (Xavier); LAZARD (Sylvain); NA (Hyeon-Suk); WHITESIDES (Sue)
AF :	Polytechnic University/Brooklyn, NY 11201/Etats-Unis (1 aut.); INRIA Sophia-Antipolis/Sophia-Antipolis/France (2 aut.); School of Computer Science, Carleton University/Ottawa, ON/Canada (3 aut.); LORIA-INRIA Lorraine, University Nancy 2/Nancy/France (4 aut., 5 aut., 6 aut., 7 aut.); School of Computing, Soongsil University/Seoul/Corée, République de (8 aut.); School of Computer Science, McGill University/Montréal, QC/Canada (9 aut.)
DT :	Publication en série; Niveau analytique
SO :	SIAM journal on computing : (Print); ISSN 0097-5397; Etats-Unis; Da. 2008; Vol. 37; No. 2; Pp. 522-551; Bibl. 25 ref.
LA :	Anglais
EA :	Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in R³ with a total of n edges consists of Θ(n²) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, Θ(n²k²) connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an O(n²k² log n) time and O(nk²) space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.
CC :	001D02A08; 001A02F02; 001D02A05
FD :	Segment droite; Calcul 3 dimensions; Visibilité; Complexité; Construction; Polytope; Algorithme; Composante connexe; Pire cas; 52Bxx; 68Wxx; Transversal(graphe); Ensemble contour
ED :	Line segment; Three-dimensional calculations; Visibility; Complexity; Construction; Polytope; Algorithm; Edge set
SD :	Segmento recta; Visibilidad; Complejidad; Construcción; Politope; Algoritmo
LO :	INIST-16063.354000183013260090
ID :	08-0208367

Links to Exploration step

Pascal:08-0208367

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA</title>
<author><name sortKey="Bronnimann, Herve" sort="Bronnimann, Herve" uniqKey="Bronnimann H" first="Hervé" last="Brönnimann">Hervé Brönnimann</name>
<affiliation><inist:fA14 i1="01"><s1>Polytechnic University</s1>
<s2>Brooklyn, NY 11201</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Devillers, Olivier" sort="Devillers, Olivier" uniqKey="Devillers O" first="Olivier" last="Devillers">Olivier Devillers</name>
<affiliation><inist:fA14 i1="02"><s1>INRIA Sophia-Antipolis</s1>
<s2>Sophia-Antipolis</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name>
<affiliation><inist:fA14 i1="03"><s1>School of Computer Science, Carleton University</s1>
<s2>Ottawa, ON</s2>
<s3>CAN</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name>
<affiliation><inist:fA14 i1="04"><s1>LORIA-INRIA Lorraine, University Nancy 2</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name>
<affiliation><inist:fA14 i1="04"><s1>LORIA-INRIA Lorraine, University Nancy 2</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation><inist:fA14 i1="04"><s1>LORIA-INRIA Lorraine, University Nancy 2</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation><inist:fA14 i1="04"><s1>LORIA-INRIA Lorraine, University Nancy 2</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name>
<affiliation><inist:fA14 i1="05"><s1>School of Computing, Soongsil University</s1>
<s2>Seoul</s2>
<s3>KOR</s3>
<sZ>8 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name>
<affiliation><inist:fA14 i1="06"><s1>School of Computer Science, McGill University</s1>
<s2>Montréal, QC</s2>
<s3>CAN</s3>
<sZ>9 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">08-0208367</idno>
<date when="2008">2008</date>
<idno type="stanalyst">PASCAL 08-0208367 INIST</idno>
<idno type="RBID">Pascal:08-0208367</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000317</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA</title>
<author><name sortKey="Bronnimann, Herve" sort="Bronnimann, Herve" uniqKey="Bronnimann H" first="Hervé" last="Brönnimann">Hervé Brönnimann</name>
<affiliation><inist:fA14 i1="01"><s1>Polytechnic University</s1>
<s2>Brooklyn, NY 11201</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Devillers, Olivier" sort="Devillers, Olivier" uniqKey="Devillers O" first="Olivier" last="Devillers">Olivier Devillers</name>
<affiliation><inist:fA14 i1="02"><s1>INRIA Sophia-Antipolis</s1>
<s2>Sophia-Antipolis</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name>
<affiliation><inist:fA14 i1="03"><s1>School of Computer Science, Carleton University</s1>
<s2>Ottawa, ON</s2>
<s3>CAN</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name>
<affiliation><inist:fA14 i1="04"><s1>LORIA-INRIA Lorraine, University Nancy 2</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name>
<affiliation><inist:fA14 i1="04"><s1>LORIA-INRIA Lorraine, University Nancy 2</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation><inist:fA14 i1="04"><s1>LORIA-INRIA Lorraine, University Nancy 2</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation><inist:fA14 i1="04"><s1>LORIA-INRIA Lorraine, University Nancy 2</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
<sZ>7 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name>
<affiliation><inist:fA14 i1="05"><s1>School of Computing, Soongsil University</s1>
<s2>Seoul</s2>
<s3>KOR</s3>
<sZ>8 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name>
<affiliation><inist:fA14 i1="06"><s1>School of Computer Science, McGill University</s1>
<s2>Montréal, QC</s2>
<s3>CAN</s3>
<sZ>9 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">SIAM journal on computing : (Print)</title>
<title level="j" type="abbreviated">SIAM j. comput. : (Print)</title>
<idno type="ISSN">0097-5397</idno>
<imprint><date when="2008">2008</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">SIAM journal on computing : (Print)</title>
<title level="j" type="abbreviated">SIAM j. comput. : (Print)</title>
<idno type="ISSN">0097-5397</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Complexity</term>
<term>Construction</term>
<term>Edge set</term>
<term>Line segment</term>
<term>Polytope</term>
<term>Three-dimensional calculations</term>
<term>Visibility</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Segment droite</term>
<term>Calcul 3 dimensions</term>
<term>Visibilité</term>
<term>Complexité</term>
<term>Construction</term>
<term>Polytope</term>
<term>Algorithme</term>
<term>Composante connexe</term>
<term>Pire cas</term>
<term>52Bxx</term>
<term>68Wxx</term>
<term>Transversal(graphe)</term>
<term>Ensemble contour</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in R<sup>3</sup>
 with a total of n edges consists of Θ(n<sup>2</sup>
) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, Θ(n<sup>2</sup>
k<sup>2</sup>
) connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an O(n<sup>2</sup>
k<sup>2</sup>
 log n) time and O(nk<sup>2</sup>
) space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0097-5397</s0>
</fA01>
<fA03 i2="1"><s0>SIAM j. comput. : (Print)</s0>
</fA03>
<fA05><s2>37</s2>
</fA05>
<fA06><s2>2</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>BRÖNNIMANN (Hervé)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>DEVILLERS (Olivier)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>DUJMOVIC (Vida)</s1>
</fA11>
<fA11 i1="04" i2="1"><s1>EVERETT (Hazel)</s1>
</fA11>
<fA11 i1="05" i2="1"><s1>GLISSE (Marc)</s1>
</fA11>
<fA11 i1="06" i2="1"><s1>GOAOC (Xavier)</s1>
</fA11>
<fA11 i1="07" i2="1"><s1>LAZARD (Sylvain)</s1>
</fA11>
<fA11 i1="08" i2="1"><s1>NA (Hyeon-Suk)</s1>
</fA11>
<fA11 i1="09" i2="1"><s1>WHITESIDES (Sue)</s1>
</fA11>
<fA14 i1="01"><s1>Polytechnic University</s1>
<s2>Brooklyn, NY 11201</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>INRIA Sophia-Antipolis</s1>
<s2>Sophia-Antipolis</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA14 i1="03"><s1>School of Computer Science, Carleton University</s1>
<s2>Ottawa, ON</s2>
<s3>CAN</s3>
<sZ>3 aut.</sZ>
</fA14>
<fA14 i1="04"><s1>LORIA-INRIA Lorraine, University Nancy 2</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
<sZ>5 aut.</sZ>
<sZ>6 aut.</sZ>
<sZ>7 aut.</sZ>
</fA14>
<fA14 i1="05"><s1>School of Computing, Soongsil University</s1>
<s2>Seoul</s2>
<s3>KOR</s3>
<sZ>8 aut.</sZ>
</fA14>
<fA14 i1="06"><s1>School of Computer Science, McGill University</s1>
<s2>Montréal, QC</s2>
<s3>CAN</s3>
<sZ>9 aut.</sZ>
</fA14>
<fA20><s1>522-551</s1>
</fA20>
<fA21><s1>2008</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>16063</s2>
<s5>354000183013260090</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2008 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>25 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>08-0208367</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>SIAM journal on computing : (Print)</s0>
</fA64>
<fA66 i1="01"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in R<sup>3</sup>
 with a total of n edges consists of Θ(n<sup>2</sup>
) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, Θ(n<sup>2</sup>
k<sup>2</sup>
) connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an O(n<sup>2</sup>
k<sup>2</sup>
 log n) time and O(nk<sup>2</sup>
) space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A08</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001A02F02</s0>
</fC02>
<fC02 i1="03" i2="X"><s0>001D02A05</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Segment droite</s0>
<s5>17</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Line segment</s0>
<s5>17</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Segmento recta</s0>
<s5>17</s5>
</fC03>
<fC03 i1="02" i2="3" l="FRE"><s0>Calcul 3 dimensions</s0>
<s5>18</s5>
</fC03>
<fC03 i1="02" i2="3" l="ENG"><s0>Three-dimensional calculations</s0>
<s5>18</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Visibilité</s0>
<s5>19</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Visibility</s0>
<s5>19</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Visibilidad</s0>
<s5>19</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Complexité</s0>
<s5>20</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Complexity</s0>
<s5>20</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Complejidad</s0>
<s5>20</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Construction</s0>
<s5>21</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Construction</s0>
<s5>21</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Construcción</s0>
<s5>21</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Polytope</s0>
<s5>22</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Polytope</s0>
<s5>22</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Politope</s0>
<s5>22</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Algorithme</s0>
<s5>23</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Algorithm</s0>
<s5>23</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Algoritmo</s0>
<s5>23</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Composante connexe</s0>
<s4>INC</s4>
<s5>70</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Pire cas</s0>
<s4>INC</s4>
<s5>71</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE"><s0>52Bxx</s0>
<s4>INC</s4>
<s5>72</s5>
</fC03>
<fC03 i1="11" i2="X" l="FRE"><s0>68Wxx</s0>
<s4>INC</s4>
<s5>73</s5>
</fC03>
<fC03 i1="12" i2="X" l="FRE"><s0>Transversal(graphe)</s0>
<s4>INC</s4>
<s5>74</s5>
</fC03>
<fC03 i1="13" i2="X" l="FRE"><s0>Ensemble contour</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="13" i2="X" l="ENG"><s0>Edge set</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fN21><s1>133</s1>
</fN21>
<fN44 i1="01"><s1>OTO</s1>
</fN44>
<fN82><s1>OTO</s1>
</fN82>
</pA>
</standard>
<server><NO>PASCAL 08-0208367 INIST</NO>
<ET>LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA</ET>
<AU>BRÖNNIMANN (Hervé); DEVILLERS (Olivier); DUJMOVIC (Vida); EVERETT (Hazel); GLISSE (Marc); GOAOC (Xavier); LAZARD (Sylvain); NA (Hyeon-Suk); WHITESIDES (Sue)</AU>
<AF>Polytechnic University/Brooklyn, NY 11201/Etats-Unis (1 aut.); INRIA Sophia-Antipolis/Sophia-Antipolis/France (2 aut.); School of Computer Science, Carleton University/Ottawa, ON/Canada (3 aut.); LORIA-INRIA Lorraine, University Nancy 2/Nancy/France (4 aut., 5 aut., 6 aut., 7 aut.); School of Computing, Soongsil University/Seoul/Corée, République de (8 aut.); School of Computer Science, McGill University/Montréal, QC/Canada (9 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>SIAM journal on computing : (Print); ISSN 0097-5397; Etats-Unis; Da. 2008; Vol. 37; No. 2; Pp. 522-551; Bibl. 25 ref.</SO>
<LA>Anglais</LA>
<EA>Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in R<sup>3</sup>
 with a total of n edges consists of Θ(n<sup>2</sup>
) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, Θ(n<sup>2</sup>
k<sup>2</sup>
) connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an O(n<sup>2</sup>
k<sup>2</sup>
 log n) time and O(nk<sup>2</sup>
) space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.</EA>
<CC>001D02A08; 001A02F02; 001D02A05</CC>
<FD>Segment droite; Calcul 3 dimensions; Visibilité; Complexité; Construction; Polytope; Algorithme; Composante connexe; Pire cas; 52Bxx; 68Wxx; Transversal(graphe); Ensemble contour</FD>
<ED>Line segment; Three-dimensional calculations; Visibility; Complexity; Construction; Polytope; Algorithm; Edge set</ED>
<SD>Segmento recta; Visibilidad; Complejidad; Construcción; Politope; Algoritmo</SD>
<LO>INIST-16063.354000183013260090</LO>
<ID>08-0208367</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000317 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000317 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:08-0208367
   |texte=   LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA

LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri