Throwing Stones Inside Simple Polygons
Identifieur interne : 005364 ( Main/Exploration ); précédent : 005363; suivant : 005365Throwing 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 ]
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
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
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003B39
- to stream Istex, to step Curation: 003A95
- to stream Istex, to step Checkpoint: 001217
- to stream Hal, to step Corpus: 004D29
- to stream Hal, to step Curation: 004D29
- to stream Hal, to step Checkpoint: 004038
- to stream Main, to step Merge: 005510
- to stream PascalFrancis, to step Corpus: 000364
- to stream PascalFrancis, to step Curation: 000661
- to stream PascalFrancis, to step Checkpoint: 000340
- to stream Main, to step Merge: 005745
- to stream Main, to step Curation: 005364
Le 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></author><author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name></author><author><name sortKey="Kim, Hyo Sil" sort="Kim, Hyo Sil" uniqKey="Kim H" first="Hyo-Sil" last="Kim">Hyo-Sil Kim</name></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name></author><author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name></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><idno type="wicri:Area/Istex/Checkpoint">001217</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001217</idno><idno type="wicri:doubleKey">0302-9743:2006:Cheong O:throwing:stones:inside</idno><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00103952</idno><idno type="url">https://hal.inria.fr/inria-00103952</idno><idno type="wicri:Area/Hal/Corpus">004D29</idno><idno type="wicri:Area/Hal/Curation">004D29</idno><idno type="wicri:Area/Hal/Checkpoint">004038</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004038</idno><idno type="wicri:Area/Main/Merge">005510</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:08-0006939</idno><idno type="wicri:Area/PascalFrancis/Corpus">000364</idno><idno type="wicri:Area/PascalFrancis/Curation">000661</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000340</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000340</idno><idno type="wicri:doubleKey">0302-9743:2006:Cheong O:throwing:stones:inside</idno><idno type="wicri:Area/Main/Merge">005745</idno><idno type="wicri:Area/Main/Curation">005364</idno><idno type="wicri:Area/Main/Exploration">005364</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"><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Division of Computer Science, KAIST, Daejeon</wicri:regionArea><wicri:noRegion>Daejeon</wicri:noRegion></affiliation><affiliation wicri:level="1"><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="3"><country xml:lang="fr">France</country><wicri:regionArea>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy</wicri:regionArea><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><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"><country xml:lang="fr">Corée du Sud</country><wicri:regionArea>Division of Computer Science, KAIST, Daejeon</wicri:regionArea><wicri:noRegion>Daejeon</wicri:noRegion></affiliation><affiliation wicri:level="1"><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="3"><country xml:lang="fr">France</country><wicri:regionArea>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy</wicri:regionArea><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><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="3"><country xml:lang="fr">France</country><wicri:regionArea>LORIA & IECN – INRIA Lorraine, Universities Nancy 1 & 2, Nancy</wicri:regionArea><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><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><keywords scheme="KwdEn" xml:lang="en"><term>Algorithmics</term><term>Data structure</term><term>Database query</term><term>Line segment</term><term>Log file</term><term>Polygon</term><term>Query</term><term>Trajectory</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Algorithmique</term><term>Fichier log</term><term>Interrogation base donnée</term><term>Polygone</term><term>Requête</term><term>Segment droite</term><term>Structure donnée</term><term>Trajectoire</term></keywords></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><affiliations><list><country><li>Corée du Sud</li><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Nancy</li></settlement></list><tree><country name="Corée du Sud"><noRegion><name sortKey="Cheong, Otfried" sort="Cheong, Otfried" uniqKey="Cheong O" first="Otfried" last="Cheong">Otfried Cheong</name></noRegion><name sortKey="Cheong, Otfried" sort="Cheong, Otfried" uniqKey="Cheong O" first="Otfried" last="Cheong">Otfried Cheong</name><name sortKey="Kim, Hyo Sil" sort="Kim, Hyo Sil" uniqKey="Kim H" first="Hyo-Sil" last="Kim">Hyo-Sil Kim</name><name sortKey="Kim, Hyo Sil" sort="Kim, Hyo Sil" uniqKey="Kim H" first="Hyo-Sil" last="Kim">Hyo-Sil Kim</name></country><country name="France"><region name="Grand Est"><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name></region><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name></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 005364 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 005364 | 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é= ISTEX:F7D84877465B0634FC9D925D4C945585088BBC95
|texte= Throwing Stones Inside Simple Polygons
}}
| This area was generated with Dilib version V0.6.33. |  |