机构名称：
¥ 2.0
摘要。在本文中，我们研究了如何有效地订购一组不精确的点。在一个维度上，一组点的顺序是它们从低到高的排序顺序。预处理模型中的一组不精确点由一组n个不确定性区域r = {r 1，r 2，。。。r n}和一组n点p = {p 1，p 2，。。。p n}，使每个ri∈R都有一个相关点pi∈P。在一个维度中，集合R是一组间隔，该间隔诱导部分顺序，以使基础真实点P的总顺序p扩展了该部分顺序。我们展示了如何预处理r引起的部分顺序，以便在点集P下，我们可以在不确定性区域最佳时间中揭示基础总顺序。特别是，我们用一个措施来参数重叠的程度，我们称之为r的歧义，我们证明r的歧义是对点p进行分类所需时间的下限。本文可以看作是部分信息下排序的几何变体，这是计算机科学中的一个研究主题。
在部分（间隔顺序）信息下进行排序∗
主要关键词
相关文件推荐
