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

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

Bajuelos, AL, Tomás, AP, Marques, F. (2004). Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: Lower and upper bounds on the number of pieces . Lecture Notes in Computer Science, 3045 127-136. 10.1007/978-3-540-24767-8_14

cited authors

Bajuelos, AL; Tomás, AP; Marques, F

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², where r is the number of reflex vertices of P. We shall now give sharper bounds both for maxP |Π(P)| and minP |Π(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. © Springer-Verlag Berlin Heidelberg 2004.

authors

Bajuelos Dominguez, Antonio

publication date

January 1, 2004

published in

Lecture Notes in Computer Science Journal

Digital Object Identifier (DOI)

https://doi.org/10.1007/978-3-540-24767-8_14

start page

end page

volume

3045

FIU Discovery