Kirkpatrick–Seidel algorithm
The Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with time complexity, where is the number of input points and is the number of points (non dominated or maximal points, as called in some texts) in the hull. Thus, the algorithm is output-sensitive: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the gift wrapping algorithm, was known much earlier, but the Kirkpatrick–Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the bounds of non-output-sensitive algorithms. The Kirkpatrick–Seidel algorithm is named after its inventors, David G. K
- Comment
- enThe Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with time complexity, where is the number of input points and is the number of points (non dominated or maximal points, as called in some texts) in the hull. Thus, the algorithm is output-sensitive: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the gift wrapping algorithm, was known much earlier, but the Kirkpatrick–Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the bounds of non-output-sensitive algorithms. The Kirkpatrick–Seidel algorithm is named after its inventors, David G. K
- Has abstract
- enThe Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with time complexity, where is the number of input points and is the number of points (non dominated or maximal points, as called in some texts) in the hull. Thus, the algorithm is output-sensitive: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the gift wrapping algorithm, was known much earlier, but the Kirkpatrick–Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the bounds of non-output-sensitive algorithms. The Kirkpatrick–Seidel algorithm is named after its inventors, David G. Kirkpatrick and Raimund Seidel. Although the algorithm is asymptotically optimal, it is not very practical for moderate-sized problems.
- Hypernym
- Algorithm
- Is primary topic of
- Kirkpatrick–Seidel algorithm
- Label
- enKirkpatrick–Seidel algorithm
- Link from a Wikipage to another Wikipage
- Algorithm
- Analysis of algorithms
- Bitangent
- Category:Convex hull algorithms
- Convex hull
- Convex hull algorithms
- David G. Kirkpatrick
- Divide-and-conquer algorithm
- Franco P. Preparata
- Gift wrapping algorithm
- Median
- Output-sensitive algorithm
- Raimund Seidel
- Recursively
- SameAs
- 3kjrN
- m.02rpd9x
- Q4060672
- Алгоритм Киркпатрика
- Алгоритм Кіркпатрика — Зейделя
- ขั้นตอนวิธีเคิร์กแพทริก-ไซเดิล
- Subject
- Category:Convex hull algorithms
- WasDerivedFrom
- Kirkpatrick–Seidel algorithm?oldid=1055313789&ns=0
- WikiPageLength
- 4485
- Wikipage page ID
- 11699089
- Wikipage revision ID
- 1055313789
- WikiPageUsesTemplate
- Template:Expand section
- Template:Reflist