Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: Lower and upper bounds on the number of pieces

• Type: Article in International Scientific Journal
• Date: 2004

Authors

Bajuelos, AL (Author) Other; Tomas, AP (Author) FCUP; Marques, F (Author) Other

Indexing

ISI Web of Knowledge - 9 Citations

Scopus - 8 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-000-CFW

DOI: 10.1007/978-3-540-24767-8_14

Abstract (EN): Given an orthogonal polygon P, let \II(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 \II(P)\ less than or equal to 1 + r + r(2), where r is the number of reflex vertices of P. We shall now give sharper bounds both for max(P) \II(P)\ and minp \II(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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 10