On showing lower bounds for external-memory computational geometry problems
On showing lower bounds for external-memory computational geometry problems
复制标题
关于显示外部存储器计算几何问题的下界
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Peter Bro Miltersen
中科院分区：
文献类型：
--
作者：
L. Arge;Peter Bro Miltersen
。在本文中，我们考虑外部存储器计算几何问题的下界。我们（cid：12）发现，在考虑此类问题时，尚不清楚使用哪种计算模型。作为提供模型的尝试，我们定义了外部存储器图灵机模型（cid：12），并推导出该模型中许多问题的下界，包括元素独特性问题。对于这些下限，我们做出标准假设，即记录是不可分割的。放弃不可分性假设，我们展示了如何打破元素独特性的下限。作为替代模型，我们 brie(cid:13)y 讨论代数计算树的外部存储器版本。
. In this paper we consider lower bounds for external-memory computational geometry problems. We (cid:12)nd that it is not quite clear which model of computation to use when considering such problems. As an attempt of providing a model, we de(cid:12)ne the external memory Turing machine model, and we derive lower bounds for a number of problems, including the element distinct-ness problem, in this model. For these lower bounds we make the standard assumption that records are indivisible. Waiving the indivisibility assumption we show how to beat the lower bound for element distinctness. As an alternative model, we brie(cid:13)y discuss an external-memory version of the algebraic computation tree.