Recognizing polygons, or how to spy
type: Item
instance of: scholarly article
title: Recognizing polygons, or how to spy
zbMATH Open document ID: 0646.68055
DOI: 10.1007/BF01901192
author: James A. Dean
author: Andrzej Lingas
author: Jörg-Rüdiger Sack
published in: The Visual Computer
publication date: 1988-01-01T00:00:00Z
review text: A new class of so-called pseudo-star-shaped polygons is introduced. A polygon is pseudo-star-shaped if there exists a point from which the whole interior of the polygon can be seen, provided it is possible to see through single edges. We show that the class of pseudo-star-shaped polygons unifies and generalizes the well known classes of convex, monotone and star-shaped polygons. We give algorithms for testing whether a polygon is pseudo-star-shaped from a given point in linear time, and for constructing all regions from which the polygon is pseudo-star-shaped in quadratic time. We show the latter algorithm to be worst-case optimal. Also, we give efficient algorithms solving standard geometrical problems such as point-location and triangulation for pseudo-star-shaped polygons.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52A30
Mathematics Subject Classification ID: 68U99
zbMATH DE Number: 4055041
zbMATH Keywords: visibility
zbMATH Keywords: computational geometry
zbMATH Keywords: geometric algorithms
zbMATH Keywords: complexity
zbMATH Keywords: polygon recognition
zbMATH Keywords: pseudo-star-shaped polygons
Wikidata QID: Q62037527
MaRDI profile type: Publication
cites work: A linear algorithm for computing the visibility polygon from a point
cites work: Decomposing a Polygon into Simpler Components
cites work: Visibility of a simple polygon
cites work: An Optimal Algorithm for Finding the Kernel of a Polygon
cites work: Q4776831
cites work: Q3694703
full work available at URL: https://doi.org/10.1007/bf01901192
OpenAlex ID: W2028695830
DBLP publication ID: journals/vc/DeanLS88
Recommended article: Recognizing weakly convex visible polygons
Recommended article: Recognizing weakly simple polygons
Recommended article: Visual distinguishability of polygons
Recommended article: Polygon Graph Recognition
Recommended article: On recognizing shapes of polytopes from their shadows
Recommended article: Polygon recognition and symmetry detection
Recommended article: Visibility concepts in orthogonal polygon recognition
Recommended article: Recognizing visibility graphs of spiral polygons
Recommended article: Detecting Weakly Simple Polygons
description: scientific article; zbMATH DE number 4055041