概率噪声下的计算几何算法

一篇新的预印本论文研究了在存在概率噪声的原始操作下的计算几何算法。许多计算几何算法依赖于访问输入坐标数据并将其转换为组合信息的原始操作。该论文考虑了原始操作随机产生错误结果的情况，并探索了如何在不显著降低效率的情况下获得高概率的正确结果。研究发现，对于一些问题（如构造凸包），可以避免因重复操作带来的效率降低；而对于其他问题（如查找最近点对），则无法避免。该研究与之前的通信复杂性研究相关，后者利用带噪声的比较来提高效率。