Throwing Stones Inside Simple Polygons
Identifieur interne : 003A95 ( Istex/Curation ); précédent : 003A94; suivant : 003A96Throwing Stones Inside Simple Polygons
Auteurs : Otfried Cheong [Corée du Sud] ; Hazel Everett [France] ; Hyo-Sil Kim [Corée du Sud] ; Sylvain Lazard [France] ; René Schott [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: Given two sets A and B of m non-intersecting line segments in the plane, we show how to compute in O(m logm) time a data structure that uses O(m) space and allows to answer the following query in O(logm) time: Given a parabola γ: y = ax 2 + bx + c, does γ separate A and B? This structure can be used to build a data structure that stores a simple polygon and allows ray-shooting queries along parabolic trajectories with vertical main axis. For a polygon with complexity n, we can answer such “stone throwing” queries in O(log2 n) time, using O(n logn) space and O(n log2 n) preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.
Url:
DOI: 10.1007/11775096_18
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003B39
Links to Exploration step
ISTEX:F7D84877465B0634FC9D925D4C945585088BBC95Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Throwing Stones Inside Simple Polygons</title><author><name sortKey="Cheong, Otfried" sort="Cheong, Otfried" uniqKey="Cheong O" first="Otfried" last="Cheong">Otfried Cheong</name><affiliation wicri:level="1"><mods:affiliation>Division of Computer Science, KAIST, Daejeon, South Korea</mods:affiliation><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Division of Computer Science, KAIST, Daejeon</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: otfried@tclab.kaist.ac.kr</mods:affiliation><country wicri:rule="url">Corée du Sud</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"><mods:affiliation>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: Hazel.Everett@loria.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Kim, Hyo Sil" sort="Kim, Hyo Sil" uniqKey="Kim H" first="Hyo-Sil" last="Kim">Hyo-Sil Kim</name><affiliation wicri:level="1"><mods:affiliation>Division of Computer Science, KAIST, Daejeon, South Korea</mods:affiliation><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Division of Computer Science, KAIST, Daejeon</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: hyosil@tclab.kaist.ac.kr</mods:affiliation><country wicri:rule="url">Corée du Sud</country></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="1"><mods:affiliation>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: Sylvain.Lazard@loria.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name><affiliation wicri:level="1"><mods:affiliation>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: Rene.Schott@loria.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:F7D84877465B0634FC9D925D4C945585088BBC95</idno><date when="2006" year="2006">2006</date><idno type="doi">10.1007/11775096_18</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-0S07LPN4-H/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003B39</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003B39</idno><idno type="wicri:Area/Istex/Curation">003A95</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Throwing Stones Inside Simple Polygons</title><author><name sortKey="Cheong, Otfried" sort="Cheong, Otfried" uniqKey="Cheong O" first="Otfried" last="Cheong">Otfried Cheong</name><affiliation wicri:level="1"><mods:affiliation>Division of Computer Science, KAIST, Daejeon, South Korea</mods:affiliation><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Division of Computer Science, KAIST, Daejeon</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: otfried@tclab.kaist.ac.kr</mods:affiliation><country wicri:rule="url">Corée du Sud</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"><mods:affiliation>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: Hazel.Everett@loria.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Kim, Hyo Sil" sort="Kim, Hyo Sil" uniqKey="Kim H" first="Hyo-Sil" last="Kim">Hyo-Sil Kim</name><affiliation wicri:level="1"><mods:affiliation>Division of Computer Science, KAIST, Daejeon, South Korea</mods:affiliation><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Division of Computer Science, KAIST, Daejeon</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: hyosil@tclab.kaist.ac.kr</mods:affiliation><country wicri:rule="url">Corée du Sud</country></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="1"><mods:affiliation>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: Sylvain.Lazard@loria.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name><affiliation wicri:level="1"><mods:affiliation>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: Rene.Schott@loria.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Given two sets A and B of m non-intersecting line segments in the plane, we show how to compute in O(m logm) time a data structure that uses O(m) space and allows to answer the following query in O(logm) time: Given a parabola γ: y = ax 2 + bx + c, does γ separate A and B? This structure can be used to build a data structure that stores a simple polygon and allows ray-shooting queries along parabolic trajectories with vertical main axis. For a polygon with complexity n, we can answer such “stone throwing” queries in O(log2 n) time, using O(n logn) space and O(n log2 n) preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003A95 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 003A95 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:F7D84877465B0634FC9D925D4C945585088BBC95
|texte= Throwing Stones Inside Simple Polygons
}}
| This area was generated with Dilib version V0.6.33. |  |