Robotics Research Technical Report: Linear Time Algorithms for Visibility and Shortest Path, Problems Inside Simple Polygons (Classic Reprint) - Hardcover
Inhaltsangabe
Excerpt from Robotics Research Technical Report: Linear Time Algorithms for Visibility and Shortest Path, Problems Inside Simple Polygons
We present linear time algorithms for solving the following problems involving a simple planar polygon P: (i) Computing the collection of all shortest paths inside P from a given source vertex 5 to all the other vertices of P; (ii) Computing the subpolygon of P consisting of points that are visible from a segment within P; (iii) Preprocessing P so that for any query ray r emerging from some fixed edge e of P, we can find in logarithmic time the first intersection of r with the boundary of P; (iv) Preprocessing P so that for any query point x in P, we can find in logarithmic time the portion of the edge e that is visible from x; (v) Preprocessing P so that for any query point x inside P and direction u, we can find in logarithmic time the first point on the boundary of P hit by the ray at direction u from x; (vi) Calculating a hierarchical decomposition of P into smaller polygons by recursive polygon cutting, as in [ch]. (vii) Calculating the (clockwise and counterclockwise) convex ropes (in the terminology of [ps]) from a fixed vertex 3 of P lying on its convex hull, to all other vertices of P. All these algorithms are based on a recent linear time algorithm of Tarjan and Van Wyk for triangulating a simple polygon, but use additional techniques to make all subsequent phases of these algorithms also linear.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.
Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.
Weitere beliebte Ausgaben desselben Titels
Suchergebnisse für Robotics Research Technical Report: Linear Time Algorithms...
Beispielbild für diese ISBN
Robotics Research Technical Report Linear Time Algorithms for Visibility and Shortest Path, Problems Inside Simple Polygons Classic Reprint
Anbieter: PBShop.store US, Wood Dale, IL, USA
Verkäuferbewertung 5 von 5 Sternen
HRD. Zustand: New. New Book. Shipped from UK. Established seller since 2000. Bestandsnummer des Verkäufers LX-9780332164588
Beispielbild für diese ISBN
Robotics Research Technical Report Linear Time Algorithms for Visibility and Shortest Path, Problems Inside Simple Polygons Classic Reprint
Anbieter: PBShop.store UK, Fairford, GLOS, Vereinigtes Königreich
Verkäuferbewertung 4 von 5 Sternen
HRD. Zustand: New. New Book. Shipped from UK. Established seller since 2000. Bestandsnummer des Verkäufers LX-9780332164588
Neu kaufen
EUR 26,50
EUR 4,78 Versand
Versand von Vereinigtes Königreich nach USA
Versand von Vereinigtes Königreich nach USA
Anzahl: 15 verfügbar