Chan's algorithm (original) (raw)
In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set of points, in 2- or 3-dimensional space. The algorithm takes time, where is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an algorithm (Graham scan, for example) with Jarvis march, in order to obtain an optimal time. Chan's algorithm is notable because it is much simpler than the Kirkpatrick–Seidel algorithm, and it naturally extends to 3-dimensional space. This paradigm has been independently developed by Frank Nielsen in his Ph.D. thesis.
| Property | Value |
|---|---|
| dbo:abstract | In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set of points, in 2- or 3-dimensional space. The algorithm takes time, where is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an algorithm (Graham scan, for example) with Jarvis march, in order to obtain an optimal time. Chan's algorithm is notable because it is much simpler than the Kirkpatrick–Seidel algorithm, and it naturally extends to 3-dimensional space. This paradigm has been independently developed by Frank Nielsen in his Ph.D. thesis. (en) Chans Algorithmus (engl.: Chan’s algorithm) ist in der algorithmischen Geometrie ein ausgabesensitives Paradigma zur Berechnung der konvexen Hülle einer Menge von Punkten der Euklidischen Ebene oder des Raumes.Er kombiniert in einem Divide-and-conquer-Ansatz verschiedene bekannte Algorithmen, um eine asymptotisch optimale Laufzeit zu erzielen.Der Algorithmus ist benannt nach Timothy M. Chan,zeitgleich und unabhängig von ihm hat Frank Nielsen dieselbe Methode in seiner Dissertation entwickelt. (de) En géométrie algorithmique, l'algorithme de Chan nommé d'après son inventeur (en), est un algorithme sensible à la sortie qui calcule l'enveloppe convexe d'un ensemble de points, en dimension 2 ou 3. La complexité temporelle est où est le nombre de points dans l'enveloppe convexe. En dimension 2, l'algorithme combine un algorithme en (par exemple le parcours de Graham) et la marche de Jarvis afin d'obtenir un algorithme en . L'algorithme de Chan est important car il est plus simple que l' et s'étend facilement à la dimension 3. Le paradigme utilisé dans l'algorithme s'appuie sur les travaux de Frank Nielsen. (fr) Алгоритм Чена — алгоритм побудови опуклої оболонки скінченної множини точок на площині. Виконується за час , де — кількість точок опуклої оболонки. Є комбінацією алгоритму, що обчислює опуклу оболонку за час (наприклад, алгоритм Грехема) з алгоритмом загортання за Джарвісом, який виконується за час . Алгоритм широко використовується, так як є найшвидшим алгоритмом для обчислення опуклої оболонки, так і тому, що є суттєво простішим ніж алгоритм Кіркпатрика-Зейделя, який працює з такою ж швидкістю. Також узагальнюється на випадок обчислення опуклої оболонки в тривимірному просторі. Алгоритм названий на честь . (uk) Алгоритм Чена — алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов (сканирование по Грэхему и заворачивание по Джарвису ). Недостатком сканирования по Грэхему является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени . Заворачивание по Джарвису требует перебора всех точек для каждой из точек выпуклой оболочки, что в худшем случае занимает . Назван по имени Тимоти М. Чана. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/ChanAlgDemo.gif?width=300 |
| dbo:wikiPageID | 8320430 (xsd:integer) |
| dbo:wikiPageLength | 18447 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123539609 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Lower_envelope dbr:Output-sensitive_algorithm dbr:Convex_hull dbr:Convex_hull_algorithms dbr:Timothy_M._Chan dbr:Computational_geometry dbr:Jarvis_march dbr:Curve_orientation dbr:Graham_scan dbr:Trapezoid dbc:Convex_hull_algorithms dbr:Kirkpatrick–Seidel_algorithm dbr:Gift_wrapping_algorithm dbr:Binary_search dbr:File:ChanAlgDemo.gif |
| dbp:date | March 2018 (en) |
| dbp:reason | Why to the right and not to the left? (en) |
| dbp:wikiPageUsesTemplate | dbt:Clarify dbt:How dbt:Reflist dbt:Why |
| dcterms: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 | In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set of points, in 2- or 3-dimensional space. The algorithm takes time, where is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an algorithm (Graham scan, for example) with Jarvis march, in order to obtain an optimal time. Chan's algorithm is notable because it is much simpler than the Kirkpatrick–Seidel algorithm, and it naturally extends to 3-dimensional space. This paradigm has been independently developed by Frank Nielsen in his Ph.D. thesis. (en) Chans Algorithmus (engl.: Chan’s algorithm) ist in der algorithmischen Geometrie ein ausgabesensitives Paradigma zur Berechnung der konvexen Hülle einer Menge von Punkten der Euklidischen Ebene oder des Raumes.Er kombiniert in einem Divide-and-conquer-Ansatz verschiedene bekannte Algorithmen, um eine asymptotisch optimale Laufzeit zu erzielen.Der Algorithmus ist benannt nach Timothy M. Chan,zeitgleich und unabhängig von ihm hat Frank Nielsen dieselbe Methode in seiner Dissertation entwickelt. (de) En géométrie algorithmique, l'algorithme de Chan nommé d'après son inventeur (en), est un algorithme sensible à la sortie qui calcule l'enveloppe convexe d'un ensemble de points, en dimension 2 ou 3. La complexité temporelle est où est le nombre de points dans l'enveloppe convexe. En dimension 2, l'algorithme combine un algorithme en (par exemple le parcours de Graham) et la marche de Jarvis afin d'obtenir un algorithme en . L'algorithme de Chan est important car il est plus simple que l' et s'étend facilement à la dimension 3. Le paradigme utilisé dans l'algorithme s'appuie sur les travaux de Frank Nielsen. (fr) Алгоритм Чена — алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов (сканирование по Грэхему и заворачивание по Джарвису ). Недостатком сканирования по Грэхему является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени . Заворачивание по Джарвису требует перебора всех точек для каждой из точек выпуклой оболочки, что в худшем случае занимает . Назван по имени Тимоти М. Чана. (ru) Алгоритм Чена — алгоритм побудови опуклої оболонки скінченної множини точок на площині. Виконується за час , де — кількість точок опуклої оболонки. Є комбінацією алгоритму, що обчислює опуклу оболонку за час (наприклад, алгоритм Грехема) з алгоритмом загортання за Джарвісом, який виконується за час . Алгоритм широко використовується, так як є найшвидшим алгоритмом для обчислення опуклої оболонки, так і тому, що є суттєво простішим ніж алгоритм Кіркпатрика-Зейделя, який працює з такою ж швидкістю. Також узагальнюється на випадок обчислення опуклої оболонки в тривимірному просторі. (uk) |
| rdfs:label | Chans Algorithmus (de) Chan's algorithm (en) Algorithme de Chan (fr) Алгоритм Чена (ru) Алгоритм Чена (uk) |
| owl:sameAs | freebase:Chan's algorithm yago-res:Chan's algorithm wikidata:Chan's algorithm dbpedia-de:Chan's algorithm dbpedia-fa:Chan's algorithm dbpedia-fr:Chan's algorithm dbpedia-hu:Chan's algorithm dbpedia-ru:Chan's algorithm dbpedia-uk:Chan's algorithm dbpedia-vi:Chan's algorithm https://global.dbpedia.org/id/vmoh |
| prov:wasDerivedFrom | wikipedia-en:Chan's_algorithm?oldid=1123539609&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/ChanAlgDemo.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Chan's_algorithm |
| is dbo:wikiPageRedirects of | dbr:Chan's_Algorithm dbr:Chan_algorithm dbr:Timothy_Chan's_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Double_exponential_function dbr:Output-sensitive_algorithm dbr:Convex_hull dbr:Convex_hull_algorithms dbr:Timothy_M._Chan dbr:Chan's_Algorithm dbr:Gift_wrapping_algorithm dbr:Chan_algorithm dbr:Timothy_Chan's_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Chan's_algorithm |
