Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles
type: Item
instance of: scholarly article
title: Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles
zbMATH Open document ID: 0757.68096
DOI: 10.1007/BF02189307
author: Alexei Gorpinevich
author: Valeriu Soltan
published in: Discrete \& Computational Geometry
publication date: 1992-12-14T00:00:00Z
full work available at URL: https://eudml.org/doc/131234
review text: The authors give a formula for a minimum number of dissecting rectangles for a given rectangular polygon with arbitrary (possibly, degenerate) holes. They also give a polynomial time algorithm for dissecting the polygon in a minimum number of rectangles. The holes can degenerate into points. This fact disproves an assertion about the \(NP\)-hardness of this problem.
reviewed by: Hans-Dietrich Hecker
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52C99
zbMATH DE Number: 78493
zbMATH Keywords: rectilinear polygons
zbMATH Keywords: rectangles
zbMATH Keywords: holes
MaRDI profile type: Publication
cites work: Minimal rectangular partitions of digitized blobs
cites work: Q5203690
cites work: Efficient Algorithms for Geometric Graph Search Problems
cites work: Q4165403
cites work: Q3948588
cites work: Q3893361
cites work: Finding a manhattan path and related problems
description: scientific article; zbMATH DE number 78493