The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D
Identifieur interne : 006639 ( Main/Exploration ); précédent : 006638; suivant : 006640The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D
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 :
Abstract
We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. This improves the previously known $O(n^3\log n)$ bound by Agarwal~\cite{A94}. More generally, we show that a set of $k$ polytopes with a total of $n$ edges admits, in the worse case, $\Theta(n^2k^2)$ connected components of lines tangent to any four of these polytopes.
Url:
DOI: 10.1145/997817.997827
Affiliations:
- Canada, Corée du Sud, France, États-Unis
- Grand Est, Lorraine (région)
- Nancy
- Institut national polytechnique de Lorraine, Université Nancy 2, Université de Lorraine
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 004B64
- to stream Hal, to step Curation: 004B64
- to stream Hal, to step Checkpoint: 004A91
- to stream Main, to step Merge: 006973
- to stream Main, to step Curation: 006639
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D</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"><hal:affiliation type="laboratory" xml:id="struct-7329" status="VALID"><orgName>Department of Computer and Information Science</orgName><desc><address><addrLine>Polytechnic Institute of NYU, Six MetroTech Center Brooklyn, NY 11201 Tel. 718.260.3600 Fax 718.260.3136 E-mail inquiry@poly.edu</addrLine><country key="US"></country></address><ref type="url">http://www.poly.edu/academics/departments/computer</ref></desc><listRelation><relation active="#struct-364432" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-364432" type="direct"><org type="institution" xml:id="struct-364432" status="INCOMING"><orgName>Polytechnic University of New York</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><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"><hal:affiliation type="laboratory" xml:id="struct-2462" status="OLD"><idno type="RNSR">200318408A</idno><orgName>GEOMETRICA</orgName><orgName type="acronym">INRIA Sophia Antipolis</orgName><date type="start">2003-07-01</date><date type="end">2008-04-08</date><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle></tutelles></hal:affiliation><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"><hal:affiliation type="laboratory" xml:id="struct-7738" status="VALID"><orgName>School of Computer Science [Ottawa]</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><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"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></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"><hal:affiliation type="laboratory" xml:id="struct-7891" status="VALID"><orgName>School of Computing - Soongsil University, Séoul</orgName><desc><address><addrLine>Room #105, Information Science Building - Soongsil University, 511 - Sangdo-dong, Dongjak-gu - Seoul 156-743 - Korea</addrLine><country key="KR"></country></address><ref type="url">http://com_e.ssu.ac.kr/</ref></desc><listRelation><relation active="#struct-300888" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300888" type="direct"><org type="institution" xml:id="struct-300888" status="VALID"><orgName>Soongsil University, Seoul</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><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"><hal:affiliation type="laboratory" xml:id="struct-7738" status="VALID"><orgName>School of Computer Science [Ottawa]</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00103995</idno><idno type="halId">inria-00103995</idno><idno type="halUri">https://hal.inria.fr/inria-00103995</idno><idno type="url">https://hal.inria.fr/inria-00103995</idno><idno type="doi">10.1145/997817.997827</idno><date when="2004-06">2004-06</date><idno type="wicri:Area/Hal/Corpus">004B64</idno><idno type="wicri:Area/Hal/Curation">004B64</idno><idno type="wicri:Area/Hal/Checkpoint">004A91</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004A91</idno><idno type="wicri:Area/Main/Merge">006973</idno><idno type="wicri:Area/Main/Curation">006639</idno><idno type="wicri:Area/Main/Exploration">006639</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D</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"><hal:affiliation type="laboratory" xml:id="struct-7329" status="VALID"><orgName>Department of Computer and Information Science</orgName><desc><address><addrLine>Polytechnic Institute of NYU, Six MetroTech Center Brooklyn, NY 11201 Tel. 718.260.3600 Fax 718.260.3136 E-mail inquiry@poly.edu</addrLine><country key="US"></country></address><ref type="url">http://www.poly.edu/academics/departments/computer</ref></desc><listRelation><relation active="#struct-364432" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-364432" type="direct"><org type="institution" xml:id="struct-364432" status="INCOMING"><orgName>Polytechnic University of New York</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><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"><hal:affiliation type="laboratory" xml:id="struct-2462" status="OLD"><idno type="RNSR">200318408A</idno><orgName>GEOMETRICA</orgName><orgName type="acronym">INRIA Sophia Antipolis</orgName><date type="start">2003-07-01</date><date type="end">2008-04-08</date><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle></tutelles></hal:affiliation><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"><hal:affiliation type="laboratory" xml:id="struct-7738" status="VALID"><orgName>School of Computer Science [Ottawa]</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><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"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></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"><hal:affiliation type="laboratory" xml:id="struct-7891" status="VALID"><orgName>School of Computing - Soongsil University, Séoul</orgName><desc><address><addrLine>Room #105, Information Science Building - Soongsil University, 511 - Sangdo-dong, Dongjak-gu - Seoul 156-743 - Korea</addrLine><country key="KR"></country></address><ref type="url">http://com_e.ssu.ac.kr/</ref></desc><listRelation><relation active="#struct-300888" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300888" type="direct"><org type="institution" xml:id="struct-300888" status="VALID"><orgName>Soongsil University, Seoul</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><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"><hal:affiliation type="laboratory" xml:id="struct-7738" status="VALID"><orgName>School of Computer Science [Ottawa]</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></analytic><idno type="DOI">10.1145/997817.997827</idno></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="it"><term>3d visibility</term><term>computational geometry</term><term>géométrie algoritmique</term><term>visibilité 3d</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. This improves the previously known $O(n^3\log n)$ bound by Agarwal~\cite{A94}. More generally, we show that a set of $k$ polytopes with a total of $n$ edges admits, in the worse case, $\Theta(n^2k^2)$ connected components of lines tangent to any four of these polytopes.</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></region><settlement><li>Nancy</li></settlement><orgName><li>Institut national polytechnique de Lorraine</li><li>Université Nancy 2</li><li>Université de Lorraine</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"><noRegion><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006639 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006639 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:inria-00103995
|texte= The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D
}}
| This area was generated with Dilib version V0.6.33. |  |