LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA
Identifieur interne : 000710 ( PascalFrancis/Curation ); précédent : 000709; suivant : 000711LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA
Auteurs : Hervé Brönnimann [États-Unis] ; Olivier Devillers [France] ; Vida Dujmovic [Canada] ; Hazel Everett [France] ; Marc Glisse [France] ; Xavier Goaoc [France] ; Sylvain Lazard [France] ; Hyeon-Suk Na [Corée du Sud] ; Sue Whitesides [Canada]Source :
- SIAM journal on computing : (Print) [ 0097-5397 ] ; 2008.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
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 R3 with a total of n edges consists of Θ(n2) 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, Θ(n2k2) 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(n2k2 log n) time and O(nk2) 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.
pA |
|
---|
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000317
Links to Exploration step
Pascal:08-0208367Le 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 wicri:level="1"><inist:fA14 i1="01"><s1>Polytechnic University</s1>
<s2>Brooklyn, NY 11201</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Devillers, Olivier" sort="Devillers, Olivier" uniqKey="Devillers O" first="Olivier" last="Devillers">Olivier Devillers</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>INRIA Sophia-Antipolis</s1>
<s2>Sophia-Antipolis</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name>
<affiliation wicri:level="1"><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>
<country>Canada</country>
</affiliation>
</author>
<author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name>
<affiliation wicri:level="1"><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>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name>
<affiliation wicri:level="1"><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>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation wicri:level="1"><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>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation wicri:level="1"><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>
<country>France</country>
</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 wicri:level="1"><inist:fA14 i1="05"><s1>School of Computing, Soongsil University</s1>
<s2>Seoul</s2>
<s3>KOR</s3>
<sZ>8 aut.</sZ>
</inist:fA14>
<country>Corée du Sud</country>
</affiliation>
</author>
<author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name>
<affiliation wicri:level="1"><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>
<country>Canada</country>
</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>
<idno type="wicri:Area/PascalFrancis/Curation">000710</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 wicri:level="1"><inist:fA14 i1="01"><s1>Polytechnic University</s1>
<s2>Brooklyn, NY 11201</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Devillers, Olivier" sort="Devillers, Olivier" uniqKey="Devillers O" first="Olivier" last="Devillers">Olivier Devillers</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>INRIA Sophia-Antipolis</s1>
<s2>Sophia-Antipolis</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name>
<affiliation wicri:level="1"><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>
<country>Canada</country>
</affiliation>
</author>
<author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name>
<affiliation wicri:level="1"><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>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name>
<affiliation wicri:level="1"><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>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation wicri:level="1"><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>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation wicri:level="1"><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>
<country>France</country>
</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 wicri:level="1"><inist:fA14 i1="05"><s1>School of Computing, Soongsil University</s1>
<s2>Seoul</s2>
<s3>KOR</s3>
<sZ>8 aut.</sZ>
</inist:fA14>
<country>Corée du Sud</country>
</affiliation>
</author>
<author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name>
<affiliation wicri:level="1"><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>
<country>Canada</country>
</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>
</inist>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000710 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000710 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= PascalFrancis |étape= Curation |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. | ![]() |