dc.creator | Bajuelos Domínguez, António Leslie | es |
dc.creator | Tomás, Ana Paula | es |
dc.creator | Marques, Fábio José Reis Luís | es |
dc.date.accessioned | 2017-03-07T12:51:00Z | |
dc.date.available | 2017-03-07T12:51:00Z | |
dc.date.issued | 2004 | |
dc.identifier.citation | 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. | |
dc.identifier.uri | http://hdl.handle.net/11441/55464 | |
dc.description.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 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. | es |
dc.description.sponsorship | Programa de Financiamento Plurianual, Fundação para a Ciéncia e Tecnologia | es |
dc.description.sponsorship | Programa POSI | es |
dc.description.sponsorship | Programa POCTI, FCT | es |
dc.description.sponsorship | Fondo Europeo de Desarrollo Regional | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | 20th European Workshop on Computational Geometry (2004). | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Orthogonal polygons | es |
dc.subject | Decomposition | es |
dc.subject | Rectilinear cut | es |
dc.subject | Square grid | es |
dc.title | Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
idus.format.extent | 4 p. | es |
dc.eventtitle | 20th European Workshop on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |