文章基本信息

标题：Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences
本地全文：下载
作者：Stefan Funke ; Felix Weitbrecht
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：181
页码：1-15
DOI：10.4230/LIPIcs.ISAAC.2020.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given an ordered sequence of points P = {pâ,, pâ,,, â¦ , p_n}, we are interested in computing T, the set of distinct triangles occurring over all Delaunay triangulations of contiguous subsequences within P. We present a deterministic algorithm for this purpose with near-optimal time complexity O( T log n). Additionally, we prove that for an arbitrary point set in random order, the expected number of Delaunay triangles occurring over all contiguous subsequences is Î~(nlog n).
关键词：Computational Geometry; Delaunay Triangulation; Randomized Analysis