Constructing the city Voronoi diagram faster

R. Görke, A. Wolff

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    2 Downloads (Pure)

    Samenvatting

    Given a set S of n point sites in the plane, the City Voronoi diagram partitions the plane into the Voronoi regions of the sites, with respect to the City metric. This metric is induced by quickest paths according to the Manhattan metric and an accelerating transportation network that consists of c non-intersecting axisparallel line segments. We describe an algorithm that constructs the City Voronoi diagram (including quickest path information) in O((c+n)polylog(c+n)) time using a wavefront expansion. For c ¿ O(vnlog3(n)) our algorithm is faster than an algorithm by Aichholzer et al. [2], which takes O(n log n+c2 log c) time.
    Originele taal-2Engels
    TitelProceedings 2nd International Symposium on Voronoi Diagrams in Science and Engineering (VD'05, Seoul, Korea, October 10-13, 2005)
    Pagina's162-172
    StatusGepubliceerd - 2005

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Constructing the city Voronoi diagram faster'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit