On decomposing polygons into uniformly monotone parts
type: Item
instance of: scholarly article
title: On decomposing polygons into uniformly monotone parts
zbMATH Open document ID: 0654.68049
DOI: 10.1016/0020-0190(88)90097-X
author: Robin Liu
author: Simeon C. Ntafos
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: We present an \(O(n^ 3)\) algorithm for finding a maximum set of independent chords in a circle with n vertices on its circumference. We use this result to partition simple polygons into the minimum number of uniformly monotone polygons. Two or more polygons are uniformly monotone if they are monotone with respect to a common axis.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52A37
zbMATH DE Number: 4068279
zbMATH Keywords: polygon decomposition
zbMATH Keywords: computational geometry
zbMATH Keywords: monotone polygons
Wikidata QID: Q29398646
MaRDI profile type: MaRDI publication profile
cites work: A linear algorithm for computing the visibility polygon from a point
cites work: Q5684962
cites work: Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition
cites work: Algorithms for a maximum clique and a maximum independent set of a circle graph
cites work: Location of a Point in a Planar Subdivision and Its Applications
cites work: Orientations of circle graphs
Recommended article: Finding a maximum set of independent chords in a circle
Recommended article: Q3786288
Recommended article: Monotone Pieces of Chains
Recommended article: A new linear algorithm for triangulating monotone polygons
Recommended article: Q3750120
description: scientific article; zbMATH DE number 4068279