Visibility detection among moving points in a map in presence of static obstacles

Abstract

Visibility Algorithms and their studies have a prominent place in Computational Geometry and Robotics. Visibility algorithms mainly rely on visibility graphs. Geometric algorithms problems can fall in three categories for points and geometric structures: offline algorithms, online and dynamic algorithms and kinetic systems. Offline algorithms are those where the points or geometric structures are given; online and dynamic algorithms are such that the points or geometric structures can be added or deleted from the system; and kinetic systems are when the points or geometric structures move while trying to maintain a basic geometric system. In this work, we present an algorithm for visibility detection between a moving source and a fixed destination in presence of n randomly moving points and static convex polygonal obstacles in a map. It is shown through a probabilistic analysis that the proposed algorithm runs with O(n2) generally but runs in O(n) as time progresses.