Ponencia
Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces
Autor/es | Bajuelos Domínguez, António Leslie
Tomás, Ana Paula Marques, Fábio José Reis Luís |
Fecha de publicación | 2004 |
Fecha de depósito | 2017-03-07 |
Publicado en |
|
Resumen | 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 Tomás, A. P., Bajuelos, A. L., Marques, F.: ... 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 Tomás, A. P., Bajuelos, A. L., Marques, F.: Approximation algorithms to minimum vertex cover problems on polygons and terrains. In P.M.A Sloot et al. (Eds): Proc. of ICCS 2003, LNCS 2657, SpringerVerlag (2003) 869-878. we showed that |Π(P)| ≤ 1 + r + r 2, 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. |
Cita | Bajuelos Domínguez, A.L., Tomás, A.P. y Marques, F.J.R.L. (2004). Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces. En 20th European Workshop on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Partitioning orthogonal polygons ... | 130.9Kb | [PDF] | Ver/ | |