VISIBILITY ALGORITHMS IN THE PLANE

By EVELYN JONES

CONTENTS BACKGROUND NOTION OF VISIBILITY POLYGON ASYMPTOTIC COMPLEXITY TRIANGULATION THE ART GALLERY PROBLEM SPECIAL TYPES OF VISIBILITY POINT VISIBILITY PROBLEMS AND RESULTS COMPUTING VISIBILITY OF A POINT IN SIMPLE POLYGONS NON-WINDING POLYGON: O(N) ALGORITHM REMOVING WINDING: O(N) ALGORITHM COMPUTING VISIBILITY OF A POINT IN POLYGONS WITH HOLES RECOGNIZING SIMPLE POLYGONS VISIBLE FROM A POINT NOTES AND COMMENTS WEAK VISIBILITY AND SHORTEST PATHS CHARACTERIZING WEAK VISIBILITY COMPUTING WEAK VISIBILITY IN SIMPLE POLYGONS SCANNING THE BOUNDARY: O(N LOG N) ALGORITHM USING SHORTEST PATH TREES: O(N) ALGORITHM COMPUTING WEAK VISIBILITY IN POLYGONS WITH HOLES RECOGNIZING WEAKLY INTERNAL VISIBLE POLYGONS USING VISIBILITY GRAPH: O(E) ALGORITHM SCANNING THE BOUNDARY: O(N) ALGORITHM COMPUTING SHORTEST PATH TREES IN SIMPLE POLYGONS: O(N) ALGORITHM IN WEAK VISIBILITY POLYGONS: O(N) ALGORITHM RECOGNIZING WEAKLY EXTERNAL VISIBLE POLYGONS LR-VISIBILITY AND SHORTEST PATHS CHARACTERIZING LR-VISIBILITY COMPUTING LR-VISIBILITY POLYGONS RECOGNIZING LR-VISIBILITY POLYGONS WALKING IN AN LR-VISIBILITY POLYGON COMPUTING SHORTEST PATH TREES USING LR-VISIBILITY VISIBILITY GRAPHS COMPUTING VISIBILITY GRAPHS OF SIMPLE POLYGONS COMPUTING VISIBILITY GRAPHS OF POLYGONS WITH HOLES WORST-CASE: O(N2) ALGORITHM OUTPUT-SENSITIVE: O(N LOG N + E) ALGORITHM COMPUTING TANGENT VISIBILITY GRAPHS CONVEX HOLES: O(N + H2 LOG H) ALGORITHM NON-CONVEX HOLES: O(N + H2 LOG H) ALGORITHM VISIBILITY GRAPH THEORY RECOGNIZING VISIBILITY GRAPHS OF SIMPLE POLYGONS NECESSARY CONDITIONS TESTING NECESSARY CONDITIONS: O(N2) ALGORITHM CHARACTERIZING VISIBILITY GRAPHS OF SIMPLE POLYGONS RECOGNIZING SPECIAL CLASSES OF VISIBILITY GRAPHS SPIRAL POLYGONS: O(N) ALGORITHM TOWER POLYGONS: O(N) ALGORITHM CHARACTERIZING A SUB-CLASS OF SEGMENT VISIBILITY GRAPHS A FEW PROPERTIES OF VERTEX-EDGE VISIBILITY GRAPHS COMPUTING MAXIMUM CLIQUE IN A VISIBILITY GRAPH COMPUTING MAXIMUM HIDDEN VERTEX SET IN A VISIBILITY GRAPH VISIBILITY AND LINK PATHS COMPUTING MINIMUM LINK PATHS IN SIMPLE POLYGONS USING WEAK VISIBILITY: O(N) ALGORITHM USING COMPLETE VISIBILITY: O(N) ALGORITHM COMPUTING MINIMUM LINK PATHS IN POLYGONS WITH HOLES COMPUTING LINK CENTER AND RADIUS OF SIMPLE POLYGONS COMPUTING MINIMUM NESTED POLYGONS BETWEEN CONVEX POLYGONS: O(N LOG K) ALGORITHM BETWEEN NON-CONVEX POLYGONS: O(N) ALGORITHM VISIBILITY AND PATH QUERIES RAY-SHOOTING QUERIES IN SIMPLE POLYGONS VISIBILITY POLYGON QUERIES FOR POINTS IN POLYGONS WITHOUT HOLES: O(LOG N + K) QUERY ALGORITHM WITH HOLES: O(N) QUERY ALGORITHM PATH QUERIES BETWEEN POINTS IN SIMPLE POLYGONS SHORTEST PATHS: O(LOG N + K) QUERY ALGORITHM LINK PATHS: O(LOG N + K) QUERY ALGORITHM