Sublinear Explicit Incremental Planar Voronoi Diagrams

• Elena, Arseneva

• John, Iacono

• Grigorios, Koumoutsos

• Stefan, Langerman

• Boris, Zolotov

抄録

A data structure is presented that explicitly maintains the graph of a Voronoi diagram of N point sites in the plane or the dual graph of a convex hull of points in three dimensions while allowing insertions of new sites/points. Our structure supports insertions in Õ(N3/4) expected amortized time, where Õ suppresses polylogarithmic terms. This is the first result to achieve sublinear time insertions; previously it was shown by Allen et al. that Θ(√N) amortized combinatorial changes per insertion could occur in the Voronoi diagram but a sublinear-time algorithm was only presented for the special case of points in convex position.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.28(2020) (online)DOI　http://dx.doi.org/10.2197/ipsjjip.28.766------------------------------

A data structure is presented that explicitly maintains the graph of a Voronoi diagram of N point sites in the plane or the dual graph of a convex hull of points in three dimensions while allowing insertions of new sites/points. Our structure supports insertions in Õ(N3/4) expected amortized time, where Õ suppresses polylogarithmic terms. This is the first result to achieve sublinear time insertions; previously it was shown by Allen et al. that Θ(√N) amortized combinatorial changes per insertion could occur in the Voronoi diagram but a sublinear-time algorithm was only presented for the special case of points in convex position.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.28(2020) (online)DOI　http://dx.doi.org/10.2197/ipsjjip.28.766------------------------------

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 61 (12), 2020-12-15

キーワード

• [特集：離散と計算の幾何・グラフ・ゲーム] data structures, voronoi diagrams, computational geometry, combinatorial change, big cell

詳細情報

• CRID: 1050850722265247232
• NII論文ID: 170000184208
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00208713/
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles