DUGiDocsHigher-order Voronoi diagrams on triangulated surfaces
dc.contributor.author
dc.date.accessioned
2018-11-21T08:23:39Z
dc.date.available
2018-11-21T08:23:39Z
dc.date.issued
2009-04-15
dc.identifier.issn
0020-0190
dc.identifier.uri
dc.description.abstract
We study the complexity of higher-order Voronoi diagrams on triangulated surfaces under the geodesic distance, when the sites may be polygonal domains of constant complexity. More precisely, we show that on a surface defined by n triangles the sum of the combinatorial complexities of the order-j Voronoi diagrams of m sites, for j = 1, ..., k, is O (k2n2+ k2m + k n m), which is asymptotically tight in the worst case
dc.format.mimetype
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier
dc.relation.isformatof
Versió postprint del document publicat a: https://doi.org/10.1016/j.ipl.2009.01.001
dc.relation.ispartof
© Information Processing Letters, 2009, vol. 109, núm. 9, p. 440-445
dc.relation.ispartofseries
Articles publicats (D-IMA)
dc.rights
Tots els drets reservats
dc.subject
dc.title
Higher-order Voronoi diagrams on triangulated surfaces
dc.type
info:eu-repo/semantics/article
dc.rights.accessRights
info:eu-repo/semantics/openAccess
dc.type.version
info:eu-repo/semantics/acceptedVersion
dc.identifier.doi
dc.identifier.idgrec
011051
dc.type.peerreviewed
peer-reviewed
dc.identifier.eissn
1872-6119