Constructing the city Voronoi diagram faster

R. Görke, A. Wolff

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    1 Downloads (Pure)


    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.
    Original languageEnglish
    Title of host publicationAbstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)
    EditorsM.T. Berg, de
    PublisherTechnische Universiteit Eindhoven
    Publication statusPublished - 2005


    Dive into the research topics of 'Constructing the city Voronoi diagram faster'. Together they form a unique fingerprint.

    Cite this