Efficient visibility queries in simple polygons
type: Item
instance of: scholarly article
title: Efficient visibility queries in simple polygons
zbMATH Open document ID: 1019.65020
DOI: 10.1016/S0925-7721(01)00070-0
author: Prosenjit Bose
author: Anna Lubiw
author: J. Ian Munro
published in: Computational Geometry
publication date: 2003-03-10T00:00:00Z
review text: Die Autoren entwickeln Algorithmen zur Lösung des folgenden Sichtbarkeitsproblems und nahe verwandter Probleme: In der euklidischen Ebene \(E^2\) werden Polygone betrachtet (einfach zusammenhängende Teilmengen in \(E^2\), deren Rand eine geschlossene Kette von Strecken ist). Ein Polygon \(P\) wird durch seine aufeinanderfolgenden Ecken definiert; keine drei Ecken seien kollinear. Die Punkte eines Polygons \(P\) seien die Punkte des Inneren und des Randes von \(P\). Die Sprechweise ``zwei Polygonpunkte sehen einander'' bedeute, dass ihre Verbindungsstrecke keinen Punkt des Polygonäußeren enthält. Gesucht werden alle Polygonecken, die von einem gegebenen Augpunkt \(x\in P\) aus sichtbar sind (bzw. die \(x\) sehen). Der entwickelte Algorithmus findet diese Ecken in der Zeit \(O(\log n)\). Die Menge der Polygonpunkte, die von einem Augpunkt \(x\in P\) aus sichtbar sind, heißt das Sichtbarkeitspolygon von \(x\). Ein Hauptresultat der Arbeit besagt, dass sich das Sichtbarkeitspolygon von \(x\) in der Zeit \(O(\log n+k)\) ermitteln läßt, wobei \(k\) die ``Größe'' des Sichtbarkeitspolygons angibt. Als zentrales Hilfsmittel wird die Zerlegung eines Polygons \(P\) in Sichtbarkeitsbereiche verwendet. Es handelt sich dabei um die maximal zusammenhängenden Teilmengen von \(P\), deren Punkte dieselben Ecken von \(P\) sehen. Ein Polygon \(P\) besitzt \(O(n^3)\) Sichtbarkeitsbereiche (die stets konvex sind) und \(O(n^2)\) Bereiche, aus deren Punkten die minimale Anzahl von Polygonecken sichtbar ist; diese Ergebnisse sind scharf. Der zur Polygonzerlegung gehörende gerichtete duale planare Graph dient als weiteres zentrales Hilfsmittel. Er wird wesentlich herangezogen bei der Ermittlung der (im Polygon \(P\) vorliegenden) Aufeinanderfolge der Polygonecken, die von einem Augpunkt \(x\) aus zu sehen sind und damit bei der Bestimmung des Sichtbarkeitspolygons von \(x\). Es folgt die Erweiterung der Lösungsideen auf Augpunkte \(x\), die außerhalb eines Polygons \(P\) liegen. Dabei ist zu…
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 1879165
zbMATH Keywords: algorithm
zbMATH Keywords: visibility
zbMATH Keywords: polygon
reviewed by: Oswald Giering
MaRDI profile type: Publication
cites work: Visibility of disjoint polygons
cites work: Algorithms for Reporting and Counting Geometric Intersections
cites work: Q5422499
cites work: Visibility and intersection problems in plane geometry
cites work: A combinatorial theorem in plane geometry
cites work: A linear algorithm for computing the visibility polygon from a point
cites work: The Robot Localization Problem
cites work: An optimal visibility graph algorithm for triangulated simple polygons
cites work: Q3140401
cites work: Corrections to Lee's visibility polygon algorithm
cites work: Optimal Search in Planar Subdivisions
cites work: Visibility of a simple polygon
cites work: Computing the visibility polygon from an edge
cites work: Location of a Point in a Planar Subdivision and Its Applications
cites work: Q3219753
cites work: Q3799261
cites work: A New Approach to Planar Point Location
cites work: Q3992847
cites work: Hiding people in polygons
cites work: Q3693476
full work available at URL: s0925-7721(01)00070-0
OpenAlex ID: W2004826883
description: scientific article; zbMATH DE number 1879165