Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/9628
Título: | Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces |
Autor: | Tomás, Ana Paula Bajuelos, António Leslie Marques, Fábio |
Palavras-chave: | Computational Geometry Orthogonal Polygons Polygon Partition |
Data: | 2004 |
Editora: | Springer Verlag |
Resumo: | 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 |
Aparece nas coleções: | ESTGA - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
2004 CSA apt-alb-fm.ps | 395.1 kB | Postscript |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.