Kirkpatrick–Seidel algorithm (original) (raw)
Построение выпуклой оболочки методом «разделяй и властвуй» — алгоритм построения выпуклой оболочки.
| Property | Value |
|---|---|
| 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 | 11699089 (xsd:integer) |
| dbo:wikiPageLength | 4485 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1055313789 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:David_G._Kirkpatrick dbr:Analysis_of_algorithms dbr:Median dbr:Output-sensitive_algorithm dbr:Convex_hull dbr:Convex_hull_algorithms dbr:Franco_P._Preparata dbr:Divide-and-conquer_algorithm dbr:Bitangent dbr:Recursively dbc:Convex_hull_algorithms dbr:Gift_wrapping_algorithm dbr:Raimund_Seidel |
| dbp:wikiPageUsesTemplate | dbt:Expand_section dbt:Reflist |
| dct:subject | dbc:Convex_hull_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatConvexHullAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| 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 | freebase:Kirkpatrick–Seidel algorithm wikidata:Kirkpatrick–Seidel algorithm dbpedia-ru:Kirkpatrick–Seidel algorithm dbpedia-th:Kirkpatrick–Seidel algorithm dbpedia-uk:Kirkpatrick–Seidel algorithm https://global.dbpedia.org/id/3kjrN |
| prov:wasDerivedFrom | wikipedia-en:Kirkpatrick–Seidel_algorithm?oldid=1055313789&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Kirkpatrick–Seidel_algorithm |
| is dbo:wikiPageRedirects of | dbr:Kirkpatrick-Seidel_algorithm dbr:Ultimate_convex_hull_algorithm dbr:Ultimate_planar_convex_hull_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:List_of_Cornell_University_alumni_(natural_sciences) dbr:David_G._Kirkpatrick dbr:Convex_hull dbr:Convex_hull_algorithms dbr:Big_O_notation dbr:Chan's_algorithm dbr:Raimund_Seidel dbr:Kirkpatrick-Seidel_algorithm dbr:Ultimate_convex_hull_algorithm dbr:Ultimate_planar_convex_hull_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Kirkpatrick–Seidel_algorithm |