| dbo:abstract
|
- 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. Kirkpatrick and Raimund Seidel. Although the algorithm is asymptotically optimal, it is not very practical for moderate-sized problems. (en)
- Построение выпуклой оболочки методом «разделяй и властвуй» — алгоритм построения выпуклой оболочки. (ru)
- Побудова опуклої оболонки методом «розділяй та володарюй» — алгоритм побудови опуклої оболонки зі швидкістю O(n log h), де n — кількість вхідних точок, та h — кількість точок в опуклій оболонці. Свою назву отримав від імен розробників — та . (uk)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4485 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Построение выпуклой оболочки методом «разделяй и властвуй» — алгоритм построения выпуклой оболочки. (ru)
- Побудова опуклої оболонки методом «розділяй та володарюй» — алгоритм побудови опуклої оболонки зі швидкістю O(n log h), де n — кількість вхідних точок, та h — кількість точок в опуклій оболонці. Свою назву отримав від імен розробників — та . (uk)
- 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 (en)
|
| rdfs:label
|
- Kirkpatrick–Seidel algorithm (en)
- Алгоритм Киркпатрика (ru)
- Алгоритм Кіркпатрика — Зейделя (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
