Sublinear Explicit Incremental Planar Voronoi Diagrams
この論文をさがす
抄録
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
- Tweet
詳細情報 詳細情報について
-
- 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