Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/9628
Title: Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces
Author: Tomás, Ana Paula
Bajuelos, António Leslie
Marques, Fábio
Keywords: Computational Geometry
Orthogonal Polygons
Polygon Partition
Issue Date: 2004
Publisher: Springer Verlag
Abstract: Given an orthogonal polygon P, let |∏(P)| be the number of rectangles that result when we partition P by extending the edges incident to reflex vertices towards INT(P). In [4] we have shown that |∏(P)| ≤ 1+r+r<sup>2</sup>, where r is the number of reflex vertices of P. We shall now give sharper bounds both to max<sub>P</sub>|∏(P)| and min<sub>P</sub>|∏(P)|. Moreover, we characterize the structure of orthogonal polygons in general position for which these new bounds are exact. We also present bounds on the area of grid n-ogons and characterize those having the largest and the smallest area.
Peer review: yes
URI: http://hdl.handle.net/10773/9628
DOI: 10.1007/978-3-540-24767-8_14
ISSN: 0302-9743
Appears in Collections:ESTGA - Artigos

Files in This Item:
File Description SizeFormat 
2004 CSA apt-alb-fm.ps395.1 kBPostscript    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.