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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2004

Autores

Bajuelos, AL (Autor) Outra; Tomas, AP (Autor) FCUP; Marques, F (Autor) Outra

Indexação

ISI Web of Knowledge - 9 Citações

Scopus - 8 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 10