11
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      On the Complexity of Randomly Weighted Voronoi Diagrams

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          In this paper, we provide an \(O(n \mathrm{polylog} n)\) bound on the expected complexity of the randomly weighted Voronoi diagram of a set of \(n\) sites in the plane, where the sites can be either points, interior-disjoint convex sets, or other more general objects. Here the randomness is on the weight of the sites, not their location. This compares favorably with the worst case complexity of these diagrams, which is quadratic. As a consequence we get an alternative proof to that of Agarwal etal [AHKS13] of the near linear complexity of the union of randomly expanded disjoint segments or convex sets (with an improved bound on the latter). The technique we develop is elegant and should be applicable to other problems.

          Related collections

          Author and article information

          Journal
          07 January 2014
          2015-03-19
          Article
          1401.1477
          02f5c312-4176-43a6-b6a3-5a8cfd694b1f

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          cs.CG

          Comments

          Comment on this article