自避行走
自避行走（，簡稱SAW）是指在格點上進行且路徑不重複交會的隨機漫步，即行走過程中不能多次通過同一個頂點。 由於當前步驟的選擇取決於整條歷史路徑以避免自交，自避行走具備記憶性，因此不屬於馬爾可夫鏈。儘管其數學分析較為複雜，SAW模型在統計物理學、高分子化學及紐結理論等領域中皆有重要應用。 基本性質與計數 分形維數 自避行走的路徑在統計上呈現分形（碎形）特徵。其分形維數與空間維數d有關： 路徑計數 對於一般的格點，目前尚無封閉形式的精確公式…
标签：#離散幾何
共 27 篇文章
彭羅斯密鋪
彭罗斯铺砌（）屬於 。铺砌是用不重疊的多邊形或其它形狀覆蓋平面，而非周期铺砌意味將此铺砌不是，平移任何距離後，所得的铺砌都和原有的不同。彭罗斯铺砌雖不是平移對稱，但具有反射對稱和五重旋转对称。彭罗斯铺砌以1970年代研究此铺砌的數學家和物理學家羅傑·彭罗斯命名。 有幾種不同的彭罗斯铺砌，是由不同的多邊形所組成。原始的铺砌用了四種不同形狀的多邊形，後來減到只用到兩種。有一種彭罗斯铺砌使用兩種不同的菱形；另一種則是使用筝形以及稱為「飛鏢」的…
華勒斯-波埃伊-格維也納定理
華勒斯·波埃伊·格維也納定理（Wallace-Bolyai-Gerwien theorem）指 和塔斯基分割圓問題不同，此證明不但無必要使用選擇公理，而且可以真實進行。 如果將問題中的多邊形換成多面體，即是希爾伯特第三問題。這時答案是否定的。 歷史 沃爾夫岡·波埃伊最先陳述此問題。1833年格維也納作出了證明，但事實上華勒斯早在1807年已證明了。
西爾維斯特-高洛伊定理
西爾維斯特–高洛伊定理（Sylvester–Gallai theorem）說明若在平面上有有限數目的點，點的數目多於2，如果过任意两点的直线都必过第三点，则所有的点共线。（等价于若平面内所有点不全共线，则必有一条直线恰好过两点。） 這個定理在無限點的情況並不成立，可以考慮格點{\mathbb Z} \times {\mathbb Z}。 證明 以下使用無窮遞降法： 在平面上有有限多點，若它們都共線，那我們就找到想要的東西；若非，定義一條…
挂谷集合
的内部旋转的转针。 在它转动的每一阶段（除了一个端点是在三尖瓣线的一个顶点时），转针与三尖瓣线相交于三个点：两个端点（蓝色）和一切点（黑色）。 转针的中点（红色）描绘了一个直径等于转针一半的长度的圆。]] 在数学中，挂谷集合（Kakeya set）或者贝西科维奇集合，是一个在欧几里德空间中的点的集合，包含了在任何方向上的单位线段。例如，欧几里德平面中的一个半径为 \dfrac12 的圆盘，或在三维空间中一个半径为 \dfrac12 的球…
克卜勒猜想
堆積法]] 克卜勒猜想（）是以十七世紀德國天文學家约翰内斯·开普勒為名的一個數學猜想。此猜想是關於在三維歐幾里德空間中最佳的裝球方式（即留下的空隙最小的裝球方式）的。此猜想認為在每個球大小相同的狀況下，沒有任何裝球方式的「密度」大于面心立方與六方最密堆積的「密度」，即 \pi/\sqrt{18} ≈74.048%。 在1998年，托马斯·黑尔斯藉由費耶斯‧托特（）所提出的方式，提出了一個關於此猜想的證明。黑爾斯利用窮舉法的方式證明此猜想…
幸福結局問題
幸福結局問題（，由保羅·艾狄胥命名，因為這個問題令喬治·塞凱賴什和愛絲特·克萊共諧連理）是問，在平面上，給定一般位置（即平面上任意三點不共線）上的多少點，才令其中必可以找到n點能組成凸n邊形？ 1935年，艾狄胥和塞凱賴什證明：給定任意正整數N，存在正整數M使得給定在平面上一般位置上的M點，其中必可以找到N點能組成凸N邊形。 將f(N)表示為M的最小可能值，已知 f(3)=3：顯然易見 f(4)=5 ：愛絲特·克萊證明；這就是最初的問題…
密鋪
的瓷磚是一種邊對邊的密鋪，混合-{zh-tw:著;zh-cn:着;}-正密鋪、半正密鋪和其它密鋪]] 在呂伐登慶祝的牆壁雕塑藝術鑲嵌 ]] 密鋪（Tessellation）或稱平面填充、細分曲面（subdivision surface），是指把一些較小的表面填滿一個較大的表面而不留任何空隙。在數學上，密鋪可以推廣到更高的維度，稱為空間填充。 有規律的密鋪具有周期性的重複模式，較特殊的種類有平面正密鋪由正多邊形組成，而且是由同一種形狀獨立…
沃罗诺伊图
沃罗诺伊图（；，也称作，狄利克雷镶嵌）是由烏克蘭数学家格奧爾吉·沃羅諾伊建立的空间分割算法。灵感来源于笛卡尔用凸域分割空间的思想。在几何、晶体学、建筑学、地理学、气象学、信息系统等许多领域有广泛的应用。 沃洛诺伊图的单元被称为泰森多边形。 建立步骤 建立泰森多边形算法的关键是对离散数据点合理地连成三角网，即构建Delaunay三角网。建立泰森多边形的步骤为： 1、离散点自动构建三角网，即构建Delaunay三角网。对离散点和形成的三角形…
爬山問題
爬山問題（）是一個數學問題，设想一個二維山脈（表示為一個連續函數），並詢問兩個登山者是否能做到：兩個人從山脈的左右兩側海平面開始，並在任何時候都保持相同的高度，最終在山頂會合。研究表明，當山脈只有有限數量的山峰和山谷時，都可以如此協調登山者的移動；但若山脈有無限數量的山峰和山谷就不一定成立。 此問題由 James V. Whittaker 在 1966 年以此形式命名並提出，但其歷史可以追溯到本間龍雄（Tatsuo Homma），他在 …
斯洛陶伯-赫拉茨马立方
斯洛陶伯－赫拉茨马立方（Slothouber–Graatsma puzzle）是一個智力遊戲，要用 6 個 1 × 2 × 2 的立方體和 3 個 1 × 1 × 1 的立方體組成一個 3 × 3 × 3 的立方體，若將可由旋轉及鏡射衍生的解都視為一個解，则斯洛陶伯－赫拉茨马立方只有唯一解。 若問題中省略 3 個 1 × 1 × 1 的立方體，對此問題沒有任何影響，因此此問題可變成：如何在 3 × 3 × 3 的立方體空間中放入 6 個…
堆砌
]] 在幾何學中，堆砌，又稱蜂巢體（）或空間填充是空間中的密鋪或鑲嵌，由多面體密堆積、或由高維度的胞緊密堆積而成，因此該幾何體內部不會存在任何空隙，如有空隙存在則不能稱為密鋪。 堆砌通常建於歐幾里得空間。它們也可以在非歐幾里得空間，如雙曲堆砌構造。任何有限的均勻多胞形可以投射到它的外接球或外接超球體，形成球形空間的均勻堆砌。 堆砌是平面鑲嵌或密鋪在三維空間或更高維度的類比。 分類 在幾何學中，堆砌有無限多種，其中只有少部分有分類。其中正…
最邻近搜索
最邻近搜索（Nearest Neighbor Search, NNS）又称为“最近点搜索”（Closest point search），是一个在尺度空间中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。 高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为邮局问题，即居民寻找离自己家最近的邮…
達文波特-欣策爾序列
在组合数学中，達文波特–欣策爾序列是指对任意两个符号交替出现的次数作出限制的序列。達文波特–欣策爾序列其最大长度的界等于序列中不同符号的数目乘以一个渐近意义上很小但并非常数的因子，该因子取决于前述的交替次数上限。達文波特–欣策爾序列最早是由和于 1965 年为研究线性微分方程而定义的。该序列及其长度的渐近界继 一文之后成为了离散几何与几何算法分析领域的标准工具。 定义 有限序列 U = u1, u2, u3, ... 满足下列条件时被称…
種樹問題
在離散幾何中，原始的果園种植问题要求的是在一個平面中過定点的3点线的可达到的最大数量。它也被称为植树造林问题，或只簡稱為果園问题。也可以是研究有多少k点线可以存在。Hallard T.克罗夫特和埃尔德什·帕尔证明了tk > c n2 / k3，n是点的数量並且tk是k点线的数量。 他们的構造物包含了一些m-点线，其中m>k。你也可以问，如果这些是不允许的问题。 整数序列 定义t3果園(n)为過n定点可達到的3点线的最大数量。 在1974…
多格形
在趣味數學中，多格形是通過將相同的多邊形連接在一起而構成的平面圖形。多格形組成的單元通常是（但不一定是）一個簡單凸多邊形，例如正方形或正三角形。下表給出了由特定簡單多邊形產生的多邊形的更具體名稱。例如，正方形多格形會產生眾所周知的多格骨牌。 連接規則 將多邊形連接在一起的規則可能會有所不同，因此必須針對每種不同類型的多格形進行說明。但是，通常以下規則適用： 兩個多邊形只能沿一條公共邊連接，並且必須共享整條邊。 沒有兩個多邊形可以重疊。 …
德勞內三角剖分
在數學和計算幾何領域，平面上的點集P的德勞內三角剖分（）是一種是点P的一个三角剖分DT，使在P中沒有點嚴格處於 DT(P) 中任意一個三角形外接圓的內部。德勞內三角剖分最大化了此三角剖分中三角形的最小角，換句話，此算法儘量避免出現「極瘦」的三角形。此算法命名來源於，以紀念他自1934年在此領域的工作。 與沃羅諾伊圖的關係 若一離散點集的點均處於一般位置，則德勞內三角化就對應到沃罗诺伊图的對偶。特殊情形包括了三點共線及四點共圓 File:…
鑲嵌 (幾何)
在幾何學中，鑲嵌（又稱密鋪）是指能用一種或多種幾何圖形覆蓋整個平面或填充整個空間，且每個幾何圖形之間不存在空隙、也不重疊的幾何結構，與密鋪（Tessellation）或稱平面填充、細分曲面（subdivision surface）不同在於後者指的是二維的空間填充，前者則可以存在任何維度與不同結構中（如欧氏几何或羅氏幾何）。 該幾何結構又稱為空間充填、空間分割，且在不同維度中有不同的名稱：在二維空間稱為密鋪或平面鑲嵌；三維空間以上則稱為堆…
貝德蘭姆立方
貝德蘭姆立方（Bedlam cube）是由英國謎題專家布魯斯·貝德蘭姆設計的實體智力遊戲。 設計 貝德蘭姆立方由13個多立方體組成，其中有十二個是五立方體，一個是四立方體。目的是將這十三個多立方體組成為一個4 x 4 x 4的立方體。在不考慮旋轉及鏡射的條件下，有19,186種不同的解答。 貝德蘭姆方塊的立方都比3 x 3 x 3的索馬立方要大一格，因此更不容易解。 歷史 BBC《》節目中的Rachel Elnaugh和Theo Pap…
彈性多面體
是目前已知結構最簡單的非面自相交的彈性多面體]] 彈性多面體（或譯柔性多面體）是沒有固定邊界的多面體，可以不改變面的形狀、不折斷或彎曲任何面或邊，而改變其形狀。根據柯西剛性定理，在三維以及更高維度的空間中，這種多面體不能是凸的。 最早發現的彈性多面體為布里卡爾八面體，於1897年由發現。其與正八面體同構，但存在自相交面，換句話說，其是一種底面為不固定形狀之反平行四邊形的雙四角錐。在\mathbb{R}^3空間中，不自相交的彈性多面體的例…