检索结果-内蒙古大学图书馆

Persistent Predecessor Search and Orthogonal Point Location on the word ram

ACM TRANSACTIONS ON algorithms 2013年第3期9卷 22-22页

作者： Chan, Timothy M. Univ Waterloo Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

We answer a basic data structuring question (e.g., raised by Dietz and raman [1991]): Can van Emde Boas trees be made persistent, without changing their asymptotic query/update time? We present a (partially) persistent data structure that supports predecessor search in a set of integers in {1,...,U} under an arbitrary sequence of n insertions and deletions, with O(log log U) expected query time and expected amortized update time, and O(n) space. The query bound is optimal in U for linear-space structures and improves previous near-O((log log U)(2)) methods. The same method solves a fundamental problem from computational geometry: point location in orthogonal planar subdivisions (where edges are vertical or horizontal). We obtain the first static data structure achieving O(log log U) worst-case query time and linear space. This result is again optimal in U for linear-space structures and improves the previous O((log log U)(2)) method by de Berg et al. [1995]. The same result also holds for higher-dimensional subdivisions that are orthogonal binary space partitions, and for certain nonorthogonal planar subdivisions such as triangulations without small angles. Many geometric applications follow, including improved query times for orthogonal range reporting for dimensions >= 3 on the ram. Our key technique is an interesting new van-Emde-Boas-style recursion that alternates between two strategies, both quite simple.

关键词： Computational geometry point location persistent data structures word-ram algorithms

来源：评论

学校读者我要写书评

暂无评论

TRANSDICHOTOMOUS RESULTS IN COMPUTATIONAL GEOMETRY, I: POINT LOCATION IN SUBLOGARITHMIC TIME

引用

SIAM JOURNAL ON COMPUTING 2009年第2期39卷 703-729页

作者： Chan, Timothy M. Patrascu, Mihai Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada MIT MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

Given a planar subdivision whose coordinates are integers bounded by U <= 2(w), we present a linear-space data structure that can answer point-location queries in O(min{lg n/lg lg n, root lg U/lg lg U}) time on the unit-cost random access machine (ram) with word size w. This is the. first result to beat the standard Theta(lg n) bound for infinite precision models. As a consequence, we obtain the first o(n lg n) (randomized) algorithms for many fundamental problems in computational geometry for arbitrary integer input on the word ram, including: constructing the convex hull of a three-dimensional (3D) point set, computing the Voronoi diagram or the Euclidean minimum spanning tree of a planar point set, triangulating a polygon with holes, and finding intersections among a set of line segments. Higher-dimensional extensions and applications are also discussed. Though computational geometry with bounded precision input has been investigated for a long time, improvements have been limited largely to problems of an orthogonal flavor. Our results surpass this long-standing limitation, answering, for example, a question of Willard (SODA'92).

关键词： computational geometry word-ram algorithms data structures sorting searching convex hulls Voronoi diagrams segment intersection

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：