• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >On Quadtrees, Voronoi Diagrams, and Lattices: Results in Geometric Algorithms
【24h】

On Quadtrees, Voronoi Diagrams, and Lattices: Results in Geometric Algorithms

机译：在四叉树，Voronoi图和格上：几何算法中的结果

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The unifying theme of this thesis is geometric algorithms, and somewhat more specifically algorithmic aspects of geometric structures including quadtrees, Voronoi diagrams, and lattices. It contains two parts, the first of which is on subdivision algorithms, and the second of which is on lattice algorithms..;Part I of this thesis is on subdivision algorithms. In Chapter 1, we study the amortized cost of smooth splits in quadtrees and their higher-dimensional analogs. A quadtree is smooth if any two adjacent leaf boxes differ by at most one in depth. A basic operation on a quadtree is to expand it by splitting any given leaf. We analyze quadtrees that restore smoothness after each split operation and also maintain neighbor pointers. Our main result shows that the smooth split operation in such quadtrees has an amortized cost of at most 2D ˙ ( D + 1)! auxiliary split operations, which corresponds to amortized constant time in quadtrees of any fixed dimension D..;In Chapter 2, we present a subdivision-based algorithm for computing iso-topic epsilon-approximatations of planar minimization diagrams. Given a family F = {ƒ1, . . . , ƒ n} of continuous functions with ƒi: R 2 → R, the minimization diagram of F partitions the plane into regions on which ƒi is minimal. Minimization diagrams generalize many natural Voronoi diagrams, and we show how to use our framework to compute an anisotropic Voronoi diagram on polygonal sites. We have implemented a prototype of our algorithm for anisotropic Voronoi diagrams, and provide experimental results. Our algorithm uses the smooth quadtree studied in Chapter 1 as its primary underlying data structure. We note that the focus of Chapter 2 is both more conceptual and more applied than other chapters.;Part II of this thesis is on lattice algorithms. In Chapter 3, we provide background material about linear algebra and lattices for the following chapters. In Section 3.3 we also give a high-level overview of the connections between fundamental domains, algorithms for the closest vector problem, and basis reduction which builds context for notions of basis reduction studied in the remaining two chapters.;In Chapter 4 we introduce and study the Lattice Distortion Problem (LDP). LDP asks how "similar" two lattices are, i.e., what the minimum distortion of a linear bijection between two lattices is. We first show that the distortion between any two lattices is approximated up to a nO(log n) factor by a simple function of their successive minima. Our methods are constructive, allowing us to compute low- distortion mappings with a tradeoff between approximation quality and running time. Our algorithms rely on a notion of basis reduction introduced by Seysen (Combinatorica 1993), which we show is intimately related to lattice distortion. Lastly, we show that LDP is NP-hard to approximate to within any constant factor (under randomized reductions).;Finally, in Chapter 5 we study how to compute lattices bases that (approximately) minimize two basis quality measures. Namely, we study the problem of finding bases B with low orthogonality defect delta(B) and with low Seysen condition number S(B) (the quality measure used to bound the distortion between two lattices in Chapter 4). Our main results are algorithms for computing bases B of a lattice which minimize delta(B) and (1 + epsilon)-approximately minimize S(B), while running in time only depending only on the rank of the lattice times a polynomial in the input length. Both algorithms are enumeration-based, and work by breaking a lattice into pieces according to gaps in its successive minima, a technique which may be of independent interest.
机译：本文的统一主题是几何算法，尤其是几何结构的算法方面，包括四叉树，Voronoi图和晶格。它包括两部分，第一部分是细分算法，第二部分是格算法。.;本论文的第一部分是细分算法。在第1章中，我们研究了四叉树中的平滑拆分及其更高维类似物的摊销成本。如果任何两个相邻的叶框的最大深度相差一个，则四叉树是平滑的。四叉树上的基本操作是通过拆分任何给定的叶来扩展它。我们分析四叉树，这些四叉树可在每次拆分操作后恢复平滑度，并维护邻居指针。我们的主要结果表明，在这种四叉树中进行平滑拆分操作的摊销成本最多为2D＆dot;。 （D +1）！辅助拆分操作，它对应于任何固定维数D的四叉树中的摊销常数时间。在第二章中，我们提出了一种基于细分的算法，用于计算平面最小化图的同位素ε近似。给定一个家庭F = {ƒ1，。 。 。 ，ƒn}与ƒi的连续函数：R 2→R，F的最小化图将平面划分为ƒi最小的区域。最小化图概括了许多自然的Voronoi图，并且我们展示了如何使用我们的框架在多边形站点上计算各向异性Voronoi图。我们已经实现了各向异性Voronoi图的算法原型，并提供了实验结果。我们的算法使用第1章研究的平滑四叉树作为其主要的基础数据结构。我们注意到第二章的重点比其他章节更具概念性和适用性。在第3章中，我们为以下各章提供有关线性代数和晶格的背景材料。在第3.3节中，我们还概述了基本域之间的联系，最接近的矢量问题的算法以及基数归约，这为其余两章研究的基数归约概念构建了上下文。在第4章中，我们介绍和研究晶格畸变问题（LDP）。 LDP询问两个晶格的“相似性”如何，即两个晶格之间线性双射的最小失真是多少。我们首先表明，任意两个晶格之间的畸变通过其连续最小值的简单函数近似为nO（log n）因子。我们的方法具有建设性，使我们能够在近似质量和运行时间之间进行权衡来计算低失真映射。我们的算法依赖于Seysen（Combinatorica 1993）提出的基约化概念，我们证明它与晶格畸变密切相关。最后，我们证明了LDP很难在任何恒定因子内（在随机归约的情况下）近似于NP。最后，在第5章中，我们研究了如何计算（近似）最小化两个基本质量量度的晶格基数。即，我们研究寻找具有低正交缺陷δ（B）和低Seysen条件数S（B）（用于限制第4章中的两个晶格之间的畸变的质量度量）的碱基B的问题。我们的主要结果是用于计算晶格基数B的算法，该算法可将delta（B）和（1 + epsilon）最小化，并将S（B）最小化，而运行时间仅取决于晶格的阶次乘以多项式。输入长度。两种算法都是基于枚举的，并且通过根据其连续最小值中的间隙将晶格分解成碎片来工作，该技术可能具有独立的意义。

著录项

  • 作者

    Bennett, Huxley David.;

  • 作者单位

    New York University.;

  • 授予单位 New York University.;
  • 学科 Computer science.
  • 学位 Ph.D.
  • 年度 2017
  • 页码 190 p.
  • 总页数 190
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号