LINES AND FREE LINE SEGMENTS TANGENT TO ARBITRARY THREE-DIMENSIONAL CONVEX POLYHEDRA
Identifieur interne : 004570 ( Main/Merge ); précédent : 004569; suivant : 004571LINES 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.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000317
- to stream PascalFrancis, to step Curation: 000710
- to stream PascalFrancis, to step Checkpoint: 000275
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><wicri:noRegion>Polytechnic University</wicri:noRegion></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><wicri:noRegion>Sophia-Antipolis</wicri:noRegion><wicri:noRegion>INRIA Sophia-Antipolis</wicri:noRegion><wicri:noRegion>INRIA Sophia-Antipolis</wicri:noRegion></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><wicri:noRegion>Ottawa, ON</wicri:noRegion></affiliation></author><author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name><affiliation wicri:level="3"><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><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name><affiliation wicri:level="3"><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><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><affiliation wicri:level="3"><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><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="3"><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><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></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="3"><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><placeName><settlement type="city">Séoul</settlement><region type="capital">Région capitale de Séoul</region></placeName></affiliation></author><author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name><affiliation wicri:level="4"><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><placeName><settlement type="city">Montréal</settlement><region type="state">Québec</region></placeName><orgName type="university">Université McGill</orgName></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><idno type="wicri:Area/PascalFrancis/Checkpoint">000275</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000275</idno><idno type="wicri:doubleKey">0097-5397:2008:Bronnimann H:lines:and:free</idno><idno type="wicri:Area/Main/Merge">004570</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><wicri:noRegion>Polytechnic University</wicri:noRegion></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><wicri:noRegion>Sophia-Antipolis</wicri:noRegion><wicri:noRegion>INRIA Sophia-Antipolis</wicri:noRegion><wicri:noRegion>INRIA Sophia-Antipolis</wicri:noRegion></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><wicri:noRegion>Ottawa, ON</wicri:noRegion></affiliation></author><author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name><affiliation wicri:level="3"><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><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name><affiliation wicri:level="3"><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><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><affiliation wicri:level="3"><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><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="3"><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><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></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="3"><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><placeName><settlement type="city">Séoul</settlement><region type="capital">Région capitale de Séoul</region></placeName></affiliation></author><author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name><affiliation wicri:level="4"><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><placeName><settlement type="city">Montréal</settlement><region type="state">Québec</region></placeName><orgName type="university">Université McGill</orgName></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><affiliations><list><country><li>Canada</li><li>Corée du Sud</li><li>France</li><li>États-Unis</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Québec</li><li>Région capitale de Séoul</li></region><settlement><li>Montréal</li><li>Nancy</li><li>Séoul</li></settlement><orgName><li>Université McGill</li></orgName></list><tree><country name="États-Unis"><noRegion><name sortKey="Bronnimann, Herve" sort="Bronnimann, Herve" uniqKey="Bronnimann H" first="Hervé" last="Brönnimann">Hervé Brönnimann</name></noRegion></country><country name="France"><noRegion><name sortKey="Devillers, Olivier" sort="Devillers, Olivier" uniqKey="Devillers O" first="Olivier" last="Devillers">Olivier Devillers</name></noRegion><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name></country><country name="Canada"><noRegion><name sortKey="Dujmovic, Vida" sort="Dujmovic, Vida" uniqKey="Dujmovic V" first="Vida" last="Dujmovic">Vida Dujmovic</name></noRegion><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name></country><country name="Corée du Sud"><region name="Région capitale de Séoul"><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004570 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 004570 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|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. |  |