A space–time trade-off for computing the visibility polygon in the multi-pass model

We study the problem of computing the visibility polygon of a simple polygon P from a viewpoint inside it, when P resides in a read-only memory without random accessibility. This model of stored data is called the multi-pass model in the literature. We present an algorithm to compute the visibility...

Full description

Saved in:
Bibliographic Details
Published in:Soft computing (Berlin, Germany) Germany), 2020, Vol.24 (1), p.293-299
Main Authors: Asgaripour, Mohammad, Mohades, Ali
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Approximation
Artificial Intelligence
Computational Intelligence
Control
Engineering
Foundations
Geometry
Linear programming
Mathematical Logic and Foundations
Mechatronics
Polygons
Read-only memory devices
Restrictions
Robotics
Robots
Visibility
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the problem of computing the visibility polygon of a simple polygon P from a viewpoint inside it, when P resides in a read-only memory without random accessibility. This model of stored data is called the multi-pass model in the literature. We present an algorithm to compute the visibility polygon in this model in O ( n r / t + n t ) time, where n is the size of input data, r is the number of reflex vertices of input data, and t is the number of additional variables which we use to compute the visibility polygon where 2 < t < r .
ISSN:1432-7643
1433-7479
DOI:10.1007/s00500-019-04382-9