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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Chans Algorithmus (de)
- Chan's algorithm (en)
- Algorithme de Chan (fr)
- Алгоритм Чена (ru)
- Алгоритм Чена (uk)
|
| 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)
|
| foaf:depiction
| |
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| date
| |
| reason
| - Why to the right and not to the left? (en)
|
| has 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)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
