On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions
Identifieur interne : 002D33 ( Istex/Corpus ); précédent : 002D32; suivant : 002D34On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions
Auteurs : Marc Glisse ; Sylvain LazardSource :
- Discrete & Computational Geometry [ 0179-5376 ] ; 2012-06-01.
English descriptors
- KwdEn :
Abstract
Abstract: We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions. We first prove that the set of maximal non-occluded line segments among n disjoint unit balls has complexity Ω(n 4), which matches the trivial O(n 4) upper bound. This improves the trivial Ω(n 2) bound and also the Ω(n 3) lower bound for the restricted setting of arbitrary-size balls (Devillers and Ramos, personal communication, 2001). This result settles, negatively, the natural conjecture that this set of line segments, or, equivalently, the visibility complex, has smaller worst-case complexity for disjoint fat objects than for skinny triangles. We also prove an Ω(n 3) lower bound on the complexity of the set of non-occluded lines among n balls of arbitrary radii, improving on the trivial Ω(n 2) bound. This new bound almost matches the recent O(n 3+ε ) upper bound (Rubin, 26th Annual ACM Symposium on Computational Geometry—SCG’10, pp. 58–67, 2010).
Url:
DOI: 10.1007/s00454-012-9414-8
Links to Exploration step
ISTEX:BE8A989299DDE2E0991313C4F53AF8DC7A89C78CLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions</title><author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name><affiliation><mods:affiliation>INRIA Saclay Île de France, Orsay, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: marc.glisse@inria.fr</mods:affiliation></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation><mods:affiliation>LORIA laboratory, INRIA Nancy Grand Est, Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: sylvain.lazard@inria.fr</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:BE8A989299DDE2E0991313C4F53AF8DC7A89C78C</idno><date when="2012" year="2012">2012</date><idno type="doi">10.1007/s00454-012-9414-8</idno><idno type="url">https://api.istex.fr/ark:/67375/VQC-6LPC8G2B-7/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002D33</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002D33</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions</title><author><name sortKey="Glisse, Marc" sort="Glisse, Marc" uniqKey="Glisse M" first="Marc" last="Glisse">Marc Glisse</name><affiliation><mods:affiliation>INRIA Saclay Île de France, Orsay, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: marc.glisse@inria.fr</mods:affiliation></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation><mods:affiliation>LORIA laboratory, INRIA Nancy Grand Est, Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: sylvain.lazard@inria.fr</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Discrete & Computational Geometry</title><title level="j" type="abbrev">Discrete Comput Geom</title><idno type="ISSN">0179-5376</idno><idno type="eISSN">1432-0444</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>New York</pubPlace><date type="published" when="2012-06-01">2012-06-01</date><biblScope unit="volume">47</biblScope><biblScope unit="issue">4</biblScope><biblScope unit="page" from="756">756</biblScope><biblScope unit="page" to="772">772</biblScope></imprint><idno type="ISSN">0179-5376</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0179-5376</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>3D visibility</term><term>Balls</term><term>Free lines</term><term>Free segments</term><term>Visibility complex</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions. We first prove that the set of maximal non-occluded line segments among n disjoint unit balls has complexity Ω(n 4), which matches the trivial O(n 4) upper bound. This improves the trivial Ω(n 2) bound and also the Ω(n 3) lower bound for the restricted setting of arbitrary-size balls (Devillers and Ramos, personal communication, 2001). This result settles, negatively, the natural conjecture that this set of line segments, or, equivalently, the visibility complex, has smaller worst-case complexity for disjoint fat objects than for skinny triangles. We also prove an Ω(n 3) lower bound on the complexity of the set of non-occluded lines among n balls of arbitrary radii, improving on the trivial Ω(n 2) bound. This new bound almost matches the recent O(n 3+ε ) upper bound (Rubin, 26th Annual ACM Symposium on Computational Geometry—SCG’10, pp. 58–67, 2010).</div></front></TEI><istex><corpusName>springer-journals</corpusName><author><json:item><name>Marc Glisse</name><affiliations><json:string>INRIA Saclay Île de France, Orsay, France</json:string><json:string>E-mail: marc.glisse@inria.fr</json:string></affiliations></json:item><json:item><name>Sylvain Lazard</name><affiliations><json:string>LORIA laboratory, INRIA Nancy Grand Est, Nancy, France</json:string><json:string>E-mail: sylvain.lazard@inria.fr</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>3D visibility</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Visibility complex</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Free lines</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Free segments</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Balls</value></json:item></subject><articleId><json:string>9414</json:string><json:string>s00454-012-9414-8</json:string></articleId><arkIstex>ark:/67375/VQC-6LPC8G2B-7</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions. We first prove that the set of maximal non-occluded line segments among n disjoint unit balls has complexity Ω(n 4), which matches the trivial O(n 4) upper bound. This improves the trivial Ω(n 2) bound and also the Ω(n 3) lower bound for the restricted setting of arbitrary-size balls (Devillers and Ramos, personal communication, 2001). This result settles, negatively, the natural conjecture that this set of line segments, or, equivalently, the visibility complex, has smaller worst-case complexity for disjoint fat objects than for skinny triangles. We also prove an Ω(n 3) lower bound on the complexity of the set of non-occluded lines among n balls of arbitrary radii, improving on the trivial Ω(n 2) bound. This new bound almost matches the recent O(n 3+ε ) upper bound (Rubin, 26th Annual ACM Symposium on Computational Geometry—SCG’10, pp. 58–67, 2010).</abstract><qualityIndicators><refBibsNative>false</refBibsNative><abstractWordCount>171</abstractWordCount><abstractCharCount>1066</abstractCharCount><keywordCount>5</keywordCount><score>9.052</score><pdfWordCount>7177</pdfWordCount><pdfCharCount>30941</pdfCharCount><pdfVersion>1.4</pdfVersion><pdfPageCount>17</pdfPageCount><pdfPageSize>439.37 x 666.142 pts</pdfPageSize></qualityIndicators><title>On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions</title><genre><json:string>research-article</json:string></genre><host><title>Discrete & Computational Geometry</title><language><json:string>unknown</json:string></language><publicationDate>2012</publicationDate><copyrightDate>2012</copyrightDate><issn><json:string>0179-5376</json:string></issn><eissn><json:string>1432-0444</json:string></eissn><journalId><json:string>454</json:string></journalId><volume>47</volume><issue>4</issue><pages><first>756</first><last>772</last></pages><genre><json:string>journal</json:string></genre><editor><json:item><name>David Kirkpatrick</name></json:item></editor><subject><json:item><value>Computational Mathematics and Numerical Analysis</value></json:item><json:item><value>Combinatorics</value></json:item></subject></host><ark><json:string>ark:/67375/VQC-6LPC8G2B-7</json:string></ark><publicationDate>2012</publicationDate><copyrightDate>2012</copyrightDate><doi><json:string>10.1007/s00454-012-9414-8</json:string></doi><id>BE8A989299DDE2E0991313C4F53AF8DC7A89C78C</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-6LPC8G2B-7/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-6LPC8G2B-7/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/VQC-6LPC8G2B-7/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher scheme="https://scientific-publisher.data.istex.fr">Springer-Verlag</publisher><pubPlace>New York</pubPlace><availability><licence><p>Springer Science+Business Media, LLC, 2012</p></licence><p scheme="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</p></availability><date>2010-07-19</date></publicationStmt><notesStmt><note type="research-article" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</note><note type="journal" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions</title><author xml:id="author-0000"><persName><forename type="first">Marc</forename><surname>Glisse</surname></persName><email>marc.glisse@inria.fr</email><affiliation>INRIA Saclay Île de France, Orsay, France</affiliation></author><author xml:id="author-0001" corresp="yes"><persName><forename type="first">Sylvain</forename><surname>Lazard</surname></persName><email>sylvain.lazard@inria.fr</email><affiliation>LORIA laboratory, INRIA Nancy Grand Est, Nancy, France</affiliation></author><idno type="istex">BE8A989299DDE2E0991313C4F53AF8DC7A89C78C</idno><idno type="ark">ark:/67375/VQC-6LPC8G2B-7</idno><idno type="DOI">10.1007/s00454-012-9414-8</idno><idno type="article-id">9414</idno><idno type="article-id">s00454-012-9414-8</idno></analytic><monogr><title level="j">Discrete & Computational Geometry</title><title level="j" type="abbrev">Discrete Comput Geom</title><idno type="pISSN">0179-5376</idno><idno type="eISSN">1432-0444</idno><idno type="journal-ID">true</idno><idno type="issue-article-count">6</idno><idno type="volume-issue-count">4</idno><editor xml:id="book-author-0000"><persName><forename type="first">David</forename><surname>Kirkpatrick</surname></persName></editor><imprint><publisher>Springer-Verlag</publisher><pubPlace>New York</pubPlace><date type="published" when="2012-06-01"></date><biblScope unit="volume">47</biblScope><biblScope unit="issue">4</biblScope><biblScope unit="page" from="756">756</biblScope><biblScope unit="page" to="772">772</biblScope></imprint></monogr></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2010-07-19</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions. We first prove that the set of maximal non-occluded line segments among n disjoint unit balls has complexity Ω(n 4), which matches the trivial O(n 4) upper bound. This improves the trivial Ω(n 2) bound and also the Ω(n 3) lower bound for the restricted setting of arbitrary-size balls (Devillers and Ramos, personal communication, 2001). This result settles, negatively, the natural conjecture that this set of line segments, or, equivalently, the visibility complex, has smaller worst-case complexity for disjoint fat objects than for skinny triangles. We also prove an Ω(n 3) lower bound on the complexity of the set of non-occluded lines among n balls of arbitrary radii, improving on the trivial Ω(n 2) bound. This new bound almost matches the recent O(n 3+ε ) upper bound (Rubin, 26th Annual ACM Symposium on Computational Geometry—SCG’10, pp. 58–67, 2010).</p></abstract><textClass xml:lang="en"><keywords scheme="keyword"><list><head>Keywords</head><item><term>3D visibility</term></item><item><term>Visibility complex</term></item><item><term>Free lines</term></item><item><term>Free segments</term></item><item><term>Balls</term></item></list></keywords></textClass><textClass><keywords scheme="Journal Subject"><list><head>Mathematics</head><item><term>Computational Mathematics and Numerical Analysis</term></item><item><term>Combinatorics</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2010-07-19">Created</change><change when="2012-06-01">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-6LPC8G2B-7/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus springer-journals not found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer-Verlag</PublisherName><PublisherLocation>New York</PublisherLocation></PublisherInfo><Journal OutputMedium="All"><JournalInfo JournalProductType="ArchiveJournal" NumberingStyle="ContentOnly"><JournalID>454</JournalID><JournalPrintISSN>0179-5376</JournalPrintISSN><JournalElectronicISSN>1432-0444</JournalElectronicISSN><JournalTitle>Discrete & Computational Geometry</JournalTitle><JournalAbbreviatedTitle>Discrete Comput Geom</JournalAbbreviatedTitle><JournalSubjectGroup><JournalSubject Type="Primary">Mathematics</JournalSubject><JournalSubject Type="Secondary">Computational Mathematics and Numerical Analysis</JournalSubject><JournalSubject Type="Secondary">Combinatorics</JournalSubject></JournalSubjectGroup></JournalInfo><Volume OutputMedium="All"><VolumeInfo TocLevels="0" VolumeType="Regular"><VolumeIDStart>47</VolumeIDStart><VolumeIDEnd>47</VolumeIDEnd><VolumeIssueCount>4</VolumeIssueCount></VolumeInfo><Issue IssueType="Regular" OutputMedium="All"><IssueInfo IssueType="Regular" TocLevels="0"><IssueIDStart>4</IssueIDStart><IssueIDEnd>4</IssueIDEnd><IssueTitle Language="En">Special Issue: 26th Annual Symposium on Computational Geometry; Guest Editor: David Kirkpatrick</IssueTitle><IssueArticleCount>6</IssueArticleCount><IssueHistory><OnlineDate><Year>2012</Year><Month>3</Month><Day>27</Day></OnlineDate><PrintDate><Year>2012</Year><Month>3</Month><Day>26</Day></PrintDate><CoverDate><Year>2012</Year><Month>6</Month></CoverDate><PricelistYear>2012</PricelistYear></IssueHistory><IssueCopyright><CopyrightHolderName>Springer Science+Business Media, LLC</CopyrightHolderName><CopyrightYear>2012</CopyrightYear></IssueCopyright></IssueInfo><IssueHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Kirkpatrick</FamilyName></EditorName></Editor></EditorGroup></IssueHeader><Article ID="s00454-012-9414-8" OutputMedium="All"><ArticleInfo ArticleType="OriginalPaper" ContainsESM="No" Language="En" NumberingStyle="ContentOnly" TocLevels="0"><ArticleID>9414</ArticleID><ArticleDOI>10.1007/s00454-012-9414-8</ArticleDOI><ArticleSequenceNumber>6</ArticleSequenceNumber><ArticleTitle Language="En">On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions</ArticleTitle><ArticleFirstPage>756</ArticleFirstPage><ArticleLastPage>772</ArticleLastPage><ArticleHistory><RegistrationDate><Year>2012</Year><Month>2</Month><Day>7</Day></RegistrationDate><Received><Year>2010</Year><Month>7</Month><Day>19</Day></Received><Revised><Year>2011</Year><Month>9</Month><Day>30</Day></Revised><Accepted><Year>2011</Year><Month>10</Month><Day>10</Day></Accepted><OnlineDate><Year>2012</Year><Month>2</Month><Day>24</Day></OnlineDate></ArticleHistory><ArticleCopyright><CopyrightHolderName>Springer Science+Business Media, LLC</CopyrightHolderName><CopyrightYear>2012</CopyrightYear></ArticleCopyright><ArticleGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ArticleGrants></ArticleInfo><ArticleHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Marc</GivenName><FamilyName>Glisse</FamilyName></AuthorName><Contact><Email>marc.glisse@inria.fr</Email></Contact></Author><Author AffiliationIDS="Aff2" CorrespondingAffiliationID="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Sylvain</GivenName><FamilyName>Lazard</FamilyName></AuthorName><Contact><Email>sylvain.lazard@inria.fr</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>INRIA Saclay Île de France</OrgName><OrgAddress><City>Orsay</City><Country Code="FR">France</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>LORIA laboratory</OrgDivision><OrgName>INRIA Nancy Grand Est</OrgName><OrgAddress><City>Nancy</City><Country Code="FR">France</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En" OutputMedium="All"><Heading>Abstract</Heading><Para>We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions.</Para><Para>We first prove that the set of maximal non-occluded line segments among <Emphasis Type="Italic">n</Emphasis> disjoint <Emphasis Type="Italic">unit</Emphasis> balls has complexity <Emphasis Type="Italic">Ω</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>4</Superscript>), which matches the trivial <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>4</Superscript>) upper bound. This improves the trivial <Emphasis Type="Italic">Ω</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>2</Superscript>) bound and also the <Emphasis Type="Italic">Ω</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>3</Superscript>) lower bound for the restricted setting of arbitrary-size balls (Devillers and Ramos, personal communication, 2001). This result settles, negatively, the natural conjecture that this set of line segments, or, equivalently, the visibility complex, has smaller worst-case complexity for disjoint fat objects than for skinny triangles.</Para><Para>We also prove an <Emphasis Type="Italic">Ω</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>3</Superscript>) lower bound on the complexity of the set of non-occluded lines among <Emphasis Type="Italic">n</Emphasis> balls of arbitrary radii, improving on the trivial <Emphasis Type="Italic">Ω</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>2</Superscript>) bound. This new bound almost matches the recent <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>3+<Emphasis Type="Italic">ε</Emphasis></Superscript>) upper bound (Rubin, 26th Annual ACM Symposium on Computational Geometry—SCG’10, pp. 58–67, 2010).</Para></Abstract><KeywordGroup Language="En"><Heading>Keywords</Heading><Keyword>3D visibility</Keyword><Keyword>Visibility complex</Keyword><Keyword>Free lines</Keyword><Keyword>Free segments</Keyword><Keyword>Balls</Keyword></KeywordGroup></ArticleHeader><NoBody></NoBody></Article></Issue></Volume></Journal></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions</title></titleInfo><name type="personal"><namePart type="given">Marc</namePart><namePart type="family">Glisse</namePart><affiliation>INRIA Saclay Île de France, Orsay, France</affiliation><affiliation>E-mail: marc.glisse@inria.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal" displayLabel="corresp"><namePart type="given">Sylvain</namePart><namePart type="family">Lazard</namePart><affiliation>LORIA laboratory, INRIA Nancy Grand Est, Nancy, France</affiliation><affiliation>E-mail: sylvain.lazard@inria.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</genre><originInfo><publisher>Springer-Verlag</publisher><place><placeTerm type="text">New York</placeTerm></place><dateCreated encoding="w3cdtf">2010-07-19</dateCreated><dateIssued encoding="w3cdtf">2012-06-01</dateIssued><copyrightDate encoding="w3cdtf">2012</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions. We first prove that the set of maximal non-occluded line segments among n disjoint unit balls has complexity Ω(n 4), which matches the trivial O(n 4) upper bound. This improves the trivial Ω(n 2) bound and also the Ω(n 3) lower bound for the restricted setting of arbitrary-size balls (Devillers and Ramos, personal communication, 2001). This result settles, negatively, the natural conjecture that this set of line segments, or, equivalently, the visibility complex, has smaller worst-case complexity for disjoint fat objects than for skinny triangles. We also prove an Ω(n 3) lower bound on the complexity of the set of non-occluded lines among n balls of arbitrary radii, improving on the trivial Ω(n 2) bound. This new bound almost matches the recent O(n 3+ε ) upper bound (Rubin, 26th Annual ACM Symposium on Computational Geometry—SCG’10, pp. 58–67, 2010).</abstract><subject lang="en"><genre>Keywords</genre><topic>3D visibility</topic><topic>Visibility complex</topic><topic>Free lines</topic><topic>Free segments</topic><topic>Balls</topic></subject><relatedItem type="host"><titleInfo><title>Discrete & Computational Geometry</title></titleInfo><titleInfo type="abbreviated"><title>Discrete Comput Geom</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Kirkpatrick</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="journal" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</genre><originInfo><publisher>Springer</publisher><dateIssued encoding="w3cdtf">2012-03-27</dateIssued><copyrightDate encoding="w3cdtf">2012</copyrightDate></originInfo><subject><genre>Mathematics</genre><topic>Computational Mathematics and Numerical Analysis</topic><topic>Combinatorics</topic></subject><identifier type="ISSN">0179-5376</identifier><identifier type="eISSN">1432-0444</identifier><identifier type="JournalID">454</identifier><identifier type="IssueArticleCount">6</identifier><identifier type="VolumeIssueCount">4</identifier><part><date>2012</date><detail type="issue"><title>Special Issue: 26th Annual Symposium on Computational Geometry; Guest Editor: David Kirkpatrick</title></detail><detail type="volume"><number>47</number><caption>vol.</caption></detail><detail type="issue"><number>4</number><caption>no.</caption></detail><extent unit="pages"><start>756</start><end>772</end></extent></part><recordInfo><recordOrigin>Springer Science+Business Media, LLC, 2012</recordOrigin></recordInfo></relatedItem><identifier type="istex">BE8A989299DDE2E0991313C4F53AF8DC7A89C78C</identifier><identifier type="ark">ark:/67375/VQC-6LPC8G2B-7</identifier><identifier type="DOI">10.1007/s00454-012-9414-8</identifier><identifier type="ArticleID">9414</identifier><identifier type="ArticleID">s00454-012-9414-8</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer Science+Business Media, LLC, 2012</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</recordContentSource><recordOrigin>Springer Science+Business Media, LLC, 2012</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-6LPC8G2B-7/record.json</uri></json:item></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002D33 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 002D33 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:BE8A989299DDE2E0991313C4F53AF8DC7A89C78C
|texte= On the Complexity of Sets of Free Lines and Line Segments Among Balls in Three Dimensions
}}
| This area was generated with Dilib version V0.6.33. |  |