3SUM
{{unsolved|計算機科學|是否存在一个算法，能够在O(n^{2-\epsilon}) （\epsilon>0）的时间复杂度内解决3SUM问题？}} 在计算复杂度理论中, 3SUM问题是指如下的问题：给定一个包含n个实数的集合，判断其中是否包含3个和为0的元素。问题也可以推广到一个更一般化的版本，rSUM，是要求判断集合中是否存在r个数的和为0。3SUM问题可以很容易地在O(n^2)的时间复杂度内解决。对于某些特化的计算模型，这已…
标签：#計算幾何
共 10 篇文章
最远优先遍历
在计算几何中，紧致度量空间的最远优先遍历（）是该空间中的一个点序列。首个点任意选取，此后每次都选取距已有点集最远的点。这个概念也适用于有限几何点集，即只需将候选点限定在该点集中。也可等价地将这些点视为一个有限度量空间。对于有限度量空间或有限几何点集，由此得到的序列是全部点的排列，又称贪心排列。 最远优先遍历的任一前缀都能得到一组彼此疏离、又接近其余各点的点集。更确切地说，任何规模相同的点集，其点间距至多为该点集的两倍。而其余点到点集的最…
連結距離
在计算几何中，兩點間的連結距離（link distance）是指多邊形內以兩點為端點的任意折線之最小線段數。 多邊形的最大連結距離稱為該多邊形的連結直徑（link diameter）。 定義 多邊形內兩點的連結距離定義為： 在多邊形內部兩點與的連結距離可以表示為。 則多邊形的連結距離為在點與點之間繪製保持在多邊形內部的折線（連續線段鏈），且這些線段不與邊界相交 兩點是任取兩點，因此需要考慮到極端情況。 例子 若多邊形的連結直徑為1，則他…
沃罗诺伊图
沃罗诺伊图（；，也称作，狄利克雷镶嵌）是由烏克蘭数学家格奧爾吉·沃羅諾伊建立的空间分割算法。灵感来源于笛卡尔用凸域分割空间的思想。在几何、晶体学、建筑学、地理学、气象学、信息系统等许多领域有广泛的应用。 沃洛诺伊图的单元被称为泰森多边形。 建立步骤 建立泰森多边形算法的关键是对离散数据点合理地连成三角网，即构建Delaunay三角网。建立泰森多边形的步骤为： 1、离散点自动构建三角网，即构建Delaunay三角网。对离散点和形成的三角形…
凸包
在一个实数向量空間V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。 : S := \bigcap_{X \subseteq K \subseteq V \atop K\ \mathrm{is\ convex}} K. X的凸包可以用X内所有点(x_1, \ldots, x_n)的线性组合来构造。 : S := \left\{ \left. \, \sum_{j=1}^n t_j x_j\, \right| x_j \in …
同时定位与地图构建
技术来给迷宫绘图。|替代=|240x240像素]] 同时定位与地图构建（，簡稱SLAM），又称同步定位与地图创建，是机器人学中的一个概念：机器人从未知环境的未知地点出发，在运动过程中通过重复观测到的地图特征（比如，墙角，柱子等）定位自身位置和姿态，再根据自身位置增量式的构建地图，从而达到同时定位和地图构建的目的。 歷史 有关于SLAM的一个开创性工作是以R.C. Smith和P. Cheeseman为代表，在1986年作出的对空间不确定…
德勞內三角剖分
在數學和計算幾何領域，平面上的點集P的德勞內三角剖分（）是一種是点P的一个三角剖分DT，使在P中沒有點嚴格處於 DT(P) 中任意一個三角形外接圓的內部。德勞內三角剖分最大化了此三角剖分中三角形的最小角，換句話，此算法儘量避免出現「極瘦」的三角形。此算法命名來源於，以紀念他自1934年在此領域的工作。 與沃羅諾伊圖的關係 若一離散點集的點均處於一般位置，則德勞內三角化就對應到沃罗诺伊图的對偶。特殊情形包括了三點共線及四點共圓 File:…
计算几何
计算几何是一门兴起于二十世纪七十年代末的计算机科学的一个分支，主要研究解决几何问题的算法。 自从1946年世界上第一台电子计算机问世以来，计算机应用的一个重要里程碑是1962年美国麻省理工学院发明了世界上第一台图形显示器。自此之后，计算机可以透过图形显示器直接输入、输出图形，并且可以在显示屏上透過游标的移动，直接修改图形。而在这之前，工程师是透过一厚叠纸上密密麻麻的数字来间接表达工程图形的。 1962年被认为是美国和欧洲CAD开始发展的…
美术馆问题
美术馆问题或博物馆问题是计算几何中的一种可见性问题，来源于现实世界中的看守美术馆的问题：如何用最少的守卫看守美术馆，并使得美术馆的每个角落都在守卫的视野之中。在计算几何的版本中，美术馆的形状被表示为一个简单多边形并且每个守卫被表示为该多边形内的一个点。称一个点集 S 能够守卫一个多边形，如果对多边形内的每个点 p ,存在点 q\in S 使得连接 p 和 q 的线段在多边形的内部。 二维情形 美术馆问题最初由美国数学家 Victor L…
不规则三角形格网
不规则三角形格网（Triangulated Irregular Network，TIN）是一种用于地理信息系统中描述表面模型的数据结构。是不规则格网中最简单的一种，在等高线追踪、三维显示及断面处理等方面有广泛的应用。同规则格网相比，不规则格网储存量大、数据结构和操作都很复杂。但是不规则格网比规则格网能更准确反应地形地貌的细节特征。不规则三角形格网的原始数据多来自测区内野外实测的地形特征点。 参考