Excerpt from Computing External-Farthest Neighbors for a Simple Polygon
This paper is divided into five sections. Section 2 discusses the basic geometric concepts that we use in this paper. In Section 3 we prove some properties of external shortest paths, which lead us to an efficient algorithm for computing the external farthest neighbors for every vertex of the polygon. Section 4 describes an O(u log n) algorithm to compute external farthest neighbors. We conclude with some final remarks in Section 5.
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.
"Sinopsis" puede pertenecer a otra edición de este libro.
Excerpt from Computing External-Farthest Neighbors for a Simple Polygon
Shortest path planning in an Obstacle-cluttered environment is a classical problem in computational geometry. In two dimensions, it is common to model the Obstacles by closed simple polygons PI Pm whose interiors represent forbidden regions, and to model a robot by a point. A feasible path Of the robot in such an environment is a path that does not meet the interior Of the Obstacles. Given two points in the plane, the distance between them is the length Of the shortest feasible path connecting them; if either Of the points lies inside an Obstacle, this distance is assumed to be infinite.
The set u,p; is called the obstacle space. A useful measure of the Obstacle space is the maximum distance between any two points lying on its boundary. This maximum distance is called the diameter Of the Obstacle space. In this paper, we are concerned with the case Of a single Obstacle.
Given a simple n-gon P and two points p and g on its boundary, we define the external distance between p and q to be the length Of a shortest path that joins p and q without intersecting the interior Of P. For a vertex p Of P, let d(p) be the set Of points on (the boundary Of) P that are farthest from p with respect to the external distance, and let the external diameter Of P be the maximum external distance between any two points Of P. The problem of computing the external diameter was first considered by Samuel and Toussaint [sts7]. They presented an 0(uz) time algorithm to solve the problem, where n denotes the number Of vertices Of P.
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.
"Sobre este título" puede pertenecer a otra edición de este libro.
Sus derechos de garantía legal: Todos los consumidores de la UE se benefician de al menos dos años de protección de garantía legal para cualquier bien de consumo que se venda en la UE. Ver más
Librería: Forgotten Books, London, Reino Unido
Paperback. Condición: New. No Jacket. Print on Demand. Efficient geometry for polygon worlds. This book presents practical methods for measuring and finding the farthest points on a simple polygon's boundary. It focuses on the external distance between points and how to compute representatives for farthest neighbors for every vertex, using ideas like pockets, left and right shortest paths, and external diameter. The results include an algorithm that runs in near-linear time and uses linear space, making a once hard problem more accessible for applications in robotics and computer graphics.- Learn how to model robot paths that stay outside polygon interiors and how to define external distance.- See how pockets and lids partition a polygon and how these ideas enable fast computations.- Explore strategies to compute farthest neighbors for all vertices with proven time bounds.- Understand how the external diameter relates to diametric pairs and why it matters for decision problems.Ideal for readers of advanced computational geometry and algorithm design, and for practitioners who need efficient geometric tools. This book is a reproduction of an important historical work, digitally reconstructed using state-of-the-art technology to preserve the original format. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in the book. print-on-demand item. Nº de ref. del artículo: 9781334014048_0
Cantidad disponible: Más de 20 disponibles
Librería: PBShop.store US, Wood Dale, IL, Estados Unidos de America
PAP. Condición: New. New Book. Shipped from UK. Established seller since 2000. Nº de ref. del artículo: LW-9781334014048
Cantidad disponible: 15 disponibles
Librería: PBShop.store UK, Fairford, GLOS, Reino Unido
PAP. Condición: New. New Book. Shipped from UK. Established seller since 2000. Nº de ref. del artículo: LW-9781334014048
Cantidad disponible: 15 disponibles