Moving discs between polygons
Identifieur interne : 001361 ( Main/Exploration ); précédent : 001360; suivant : 001362Moving discs between polygons
Auteurs : Hans Rohnert [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1988.
English descriptors
- Teeft :
- Algorithm, Answer queries, Auxiliary trees, Binary search, Chain tree, Computational geometry, Constant time, Convex corner, Curve segments, Data structure, Data structures, Destination point, Edge tree, Edge weights, Endpoint, Euclidean plane, External voronoi diagram, Feasible path, Feasible paths, Final phase, Interior nodes, Line segment, Line segments, Linear time, Maximal distance, Minimal distance, Minimal edge weight, Minimum distance, Node, Obstacle space, Open line segments, Original polygons, Piano problem, Planar graph, Polygon, Polygonal region, Preprocessing, Preprocessing algorithm, Query, Query algorithm, Same component, Siam journal, Space complexity, Straight line segments, Successor relation, Technical report, Third side, Tree edges, Voronoi, Voronoi cell, Voronoi cells, Voronoi diagram, Voronoi edge, Voronoi edges, Voronoi vertices.
Abstract
Abstract: An algorithm is given for finding a collision free path for a disc between a collection of polygons having n corners in total. The polygons are fixed and can be preprocessed. One query specifies the radius r of the disc to be moved and start and destination point of the center of the disc. The answer whether a feasible path exists is given in time O(log n). Returning a feasible path is done in additional time proportional to the length of the description of the path. Preprocessing time is O(n log n) and space complexity is O(n).
Url:
DOI: 10.1007/3-540-19488-6_137
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001713
- to stream Istex, to step Curation: 001608
- to stream Istex, to step Checkpoint: 001133
- to stream Main, to step Merge: 001365
- to stream Main, to step Curation: 001361
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Moving discs between polygons</title><author><name sortKey="Rohnert, Hans" sort="Rohnert, Hans" uniqKey="Rohnert H" first="Hans" last="Rohnert">Hans Rohnert</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:DFC6AC6BB9ACFF761BF26079EB46466D2E37F4C2</idno><date when="1988" year="1988">1988</date><idno type="doi">10.1007/3-540-19488-6_137</idno><idno type="url">https://api.istex.fr/document/DFC6AC6BB9ACFF761BF26079EB46466D2E37F4C2/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001713</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001713</idno><idno type="wicri:Area/Istex/Curation">001608</idno><idno type="wicri:Area/Istex/Checkpoint">001133</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001133</idno><idno type="wicri:doubleKey">0302-9743:1988:Rohnert H:moving:discs:between</idno><idno type="wicri:Area/Main/Merge">001365</idno><idno type="wicri:Area/Main/Curation">001361</idno><idno type="wicri:Area/Main/Exploration">001361</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Moving discs between polygons</title><author><name sortKey="Rohnert, Hans" sort="Rohnert, Hans" uniqKey="Rohnert H" first="Hans" last="Rohnert">Hans Rohnert</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 10, Universität des Saarlandes</wicri:regionArea><wicri:noRegion>Universität des Saarlandes</wicri:noRegion><wicri:noRegion>Universität des Saarlandes</wicri:noRegion></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1988</date></imprint><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="Teeft" xml:lang="en"><term>Algorithm</term><term>Answer queries</term><term>Auxiliary trees</term><term>Binary search</term><term>Chain tree</term><term>Computational geometry</term><term>Constant time</term><term>Convex corner</term><term>Curve segments</term><term>Data structure</term><term>Data structures</term><term>Destination point</term><term>Edge tree</term><term>Edge weights</term><term>Endpoint</term><term>Euclidean plane</term><term>External voronoi diagram</term><term>Feasible path</term><term>Feasible paths</term><term>Final phase</term><term>Interior nodes</term><term>Line segment</term><term>Line segments</term><term>Linear time</term><term>Maximal distance</term><term>Minimal distance</term><term>Minimal edge weight</term><term>Minimum distance</term><term>Node</term><term>Obstacle space</term><term>Open line segments</term><term>Original polygons</term><term>Piano problem</term><term>Planar graph</term><term>Polygon</term><term>Polygonal region</term><term>Preprocessing</term><term>Preprocessing algorithm</term><term>Query</term><term>Query algorithm</term><term>Same component</term><term>Siam journal</term><term>Space complexity</term><term>Straight line segments</term><term>Successor relation</term><term>Technical report</term><term>Third side</term><term>Tree edges</term><term>Voronoi</term><term>Voronoi cell</term><term>Voronoi cells</term><term>Voronoi diagram</term><term>Voronoi edge</term><term>Voronoi edges</term><term>Voronoi vertices</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: An algorithm is given for finding a collision free path for a disc between a collection of polygons having n corners in total. The polygons are fixed and can be preprocessed. One query specifies the radius r of the disc to be moved and start and destination point of the center of the disc. The answer whether a feasible path exists is given in time O(log n). Returning a feasible path is done in additional time proportional to the length of the description of the path. Preprocessing time is O(n log n) and space complexity is O(n).</div></front></TEI><affiliations><list><country><li>Allemagne</li></country></list><tree><country name="Allemagne"><noRegion><name sortKey="Rohnert, Hans" sort="Rohnert, Hans" uniqKey="Rohnert H" first="Hans" last="Rohnert">Hans Rohnert</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Sarre/explor/MusicSarreV3/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001361 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001361 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Sarre
|area= MusicSarreV3
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:DFC6AC6BB9ACFF761BF26079EB46466D2E37F4C2
|texte= Moving discs between polygons
}}
| This area was generated with Dilib version V0.6.33. |  |