This HTML5 document contains 81 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n26http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
n25https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n9http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
Subject Item
dbr:Double_exponential_function
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
Subject Item
dbr:Output-sensitive_algorithm
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
Subject Item
dbr:Convex_hull
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
Subject Item
dbr:Convex_hull_algorithms
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
Subject Item
dbr:Timothy_M._Chan
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
Subject Item
dbr:Chan's_algorithm
rdf:type
yago:Event100029378 yago:WikicatConvexHullAlgorithms yago:Activity100407535 yago:Abstraction100002137 yago:Act100030358 dbo:Software yago:Rule105846932 yago:YagoPermanentlyLocatedEntity yago:Algorithm105847438 yago:Procedure101023820 yago:PsychologicalFeature100023100
rdfs:label
Chans Algorithmus Algorithme de Chan Алгоритм Чена Chan's algorithm Алгоритм Чена
rdfs:comment
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. 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. Алгоритм Чена — алгоритм побудови опуклої оболонки скінченної множини точок на площині. Виконується за час , де — кількість точок опуклої оболонки. Є комбінацією алгоритму, що обчислює опуклу оболонку за час (наприклад, алгоритм Грехема) з алгоритмом загортання за Джарвісом, який виконується за час . Алгоритм широко використовується, так як є найшвидшим алгоритмом для обчислення опуклої оболонки, так і тому, що є суттєво простішим ніж алгоритм Кіркпатрика-Зейделя, який працює з такою ж швидкістю. Також узагальнюється на випадок обчислення опуклої оболонки в тривимірному просторі. Алгоритм Чена — алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов (сканирование по Грэхему и заворачивание по Джарвису ). Недостатком сканирования по Грэхему является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени . Заворачивание по Джарвису требует перебора всех точек для каждой из точек выпуклой оболочки, что в худшем случае занимает . Назван по имени Тимоти М. Чана. 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.
foaf:depiction
n9:ChanAlgDemo.gif
dcterms:subject
dbc:Convex_hull_algorithms
dbo:wikiPageID
8320430
dbo:wikiPageRevisionID
1123539609
dbo:wikiPageWikiLink
dbr:Output-sensitive_algorithm dbr:Convex_hull dbr:Timothy_M._Chan dbr:Convex_hull_algorithms dbr:Gift_wrapping_algorithm dbr:Kirkpatrick–Seidel_algorithm dbr:Binary_search dbr:Graham_scan dbr:Jarvis_march dbr:Trapezoid dbc:Convex_hull_algorithms dbr:Lower_envelope dbr:Computational_geometry dbr:Curve_orientation n26:ChanAlgDemo.gif
owl:sameAs
dbpedia-ru:Алгоритм_Чена dbpedia-de:Chans_Algorithmus dbpedia-vi:Thuật_toán_Chan freebase:m.026_b2v yago-res:Chan's_algorithm dbpedia-hu:Chan-algoritmus dbpedia-fr:Algorithme_de_Chan dbpedia-uk:Алгоритм_Чена dbpedia-fa:الگوریتم_چان n25:vmoh wikidata:Q2025538
dbp:wikiPageUsesTemplate
dbt:Why dbt:Clarify dbt:How dbt:Reflist
dbo:thumbnail
n9:ChanAlgDemo.gif?width=300
dbp:date
March 2018
dbp:reason
Why to the right and not to the left?
dbo:abstract
Алгоритм Чена — алгоритм побудови опуклої оболонки скінченної множини точок на площині. Виконується за час , де — кількість точок опуклої оболонки. Є комбінацією алгоритму, що обчислює опуклу оболонку за час (наприклад, алгоритм Грехема) з алгоритмом загортання за Джарвісом, який виконується за час . Алгоритм широко використовується, так як є найшвидшим алгоритмом для обчислення опуклої оболонки, так і тому, що є суттєво простішим ніж алгоритм Кіркпатрика-Зейделя, який працює з такою ж швидкістю. Також узагальнюється на випадок обчислення опуклої оболонки в тривимірному просторі. Алгоритм названий на честь . 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. 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. Алгоритм Чена — алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов (сканирование по Грэхему и заворачивание по Джарвису ). Недостатком сканирования по Грэхему является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени . Заворачивание по Джарвису требует перебора всех точек для каждой из точек выпуклой оболочки, что в худшем случае занимает . Назван по имени Тимоти М. Чана. 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.
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
wikipedia-en:Chan's_algorithm?oldid=1123539609&ns=0
dbo:wikiPageLength
18447
foaf:isPrimaryTopicOf
wikipedia-en:Chan's_algorithm
Subject Item
dbr:Chan's_Algorithm
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
dbo:wikiPageRedirects
dbr:Chan's_algorithm
Subject Item
dbr:Gift_wrapping_algorithm
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
Subject Item
dbr:Chan_algorithm
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
dbo:wikiPageRedirects
dbr:Chan's_algorithm
Subject Item
dbr:Timothy_Chan's_algorithm
dbo:wikiPageWikiLink
dbr:Chan's_algorithm
dbo:wikiPageRedirects
dbr:Chan's_algorithm
Subject Item
wikipedia-en:Chan's_algorithm
foaf:primaryTopic
dbr:Chan's_algorithm