Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Mètode de Graham (ca)
- Graham Scan (de)
- Método de Graham (es)
- Parcours de Graham (fr)
- Graham scan (en)
- 그레이엄 스캔 (ko)
- Algorytm Grahama (pl)
- Exame de Graham (pt)
- Алгоритм Грэхема (ru)
- 葛立恆掃描法 (zh)
- Алгоритм Грехема (uk)
|
| rdfs:comment
| - El mètode de Graham (Graham scan) és un mètode de càlcul computacional de l'envolupant convexa d'un grup finit de punts en el pla, amb una complexitat computacional O(n log n). El nom fa honor a , qui va publicar l'algorisme el 1972. L'algorisme calcula tots els vèrtexs de l'envolupant convexa ordenats al llarg de la frontera. Pot ser modificat fàcilment per trobar els punts que, sense ser vèrtexs, pertanyen a aquesta envolupant. (ca)
- Der Graham Scan (nach Ronald Graham 1972) ist ein effizienter Algorithmus zur Berechnung der konvexen Hülle einer endlichen Menge von Punkten in der Ebene. Bei Punkten liegt seine asymptotische Laufzeit in . (de)
- El método de Graham (Graham scan) es un método de cálculo computacional de la envolvente convexa de un conjunto finito de puntos en el plano, de complejidad O(nlogn). El nombre hace honor a Ronald Graham, quien publicó el algoritmo en 1972. El algoritmo calcula todos los vértices de la envolvente convexa ordenados a lo largo de la frontera. Puede ser fácilmente modificado para calcular los puntos que, sin ser vértices, pertenecen a dicha envolvente. (es)
- Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently. (en)
- En informatique, et en géométrie algorithmique, le parcours de Graham (aussi appelé algorithme de Graham) est un algorithme pour le calcul de l'enveloppe convexe d'un ensemble de points dans le plan. Son principal intérêt est sa complexité algorithmique en O(n log n) où n est le nombre de points. Cet algorithme doit son nom à Ronald Graham, qui a publié l'algorithme original en 1972. (fr)
- 그레이엄의 스캔(Graham Scan)은 평면상에서 유한한 점들의 볼록 껍질을 찾는 방법으로, 시간 복잡도는 O(n log n)이다. 이것의 이름은 로널드 그레이엄이 1972년 원시 알고리즘을 출판한 뒤에 붙여졌다. 이 알고리즘은 볼록껍질의 모든 정점들을 테두리를 따라 찾는다. 그이 알고리즘은 경계의 오목성을 효율적으로 감지하고 제거하기 위해 스택을 사용한다. (ko)
- Алгоритм Грэхема — алгоритм построения выпуклой оболочки в двумерном пространстве.В этом алгоритме задача о выпуклой оболочке решается с помощью стека, сформированного из точек-кандидатов. Все точки входного множества заносятся в стек, а потом точки, не являющиеся вершинами выпуклой оболочки, со временем удаляются из него. По завершении работы алгоритма в стеке остаются только вершины оболочки в порядке их обхода против часовой стрелки. (ru)
- O Exame de Graham, cuja denominação vem de Ronald Graham, é uma técnica de computação usada para determinar o envoltória convexa de um dado conjunto de pontos no plano como complexidade de tempo (n log n). (pt)
- 葛立恒扫描法（Graham's scan）是一种计算一组的平面点的凸包的演算法，时间复杂度为。以在1972年发表该算法的葛立恒命名。 (zh)
- Алгоритм Грехема (англ. Graham scan) — метод знаходження опуклої оболонки для скінченної множини точок на площині за час O(n log n). Названий на честь Рональда Грехема, який опублікував первісний варіант алгоритму в 1972 році. Алгоритм знаходить всі вершини опуклої оболонки впорядковані вздовж її межі. (uk)
- Algorytm Grahama – efektywny algorytm wyszukiwania otoczki wypukłej skończonego zbioru punktów płaszczyzny; nie istnieją warianty dla przestrzeni o wyższych wymiarach. Pomysłodawcą algorytmu jest Ronald Graham. Czasowa złożoność obliczeniowa wynosi Algorytm przebiega następująco: W praktyce można również utożsamić krok 4. z 1., tzn. przyjąć, że
* Przykładowy przebieg algorytmu
*
*
*
*
*
*
*
*
*
*
*
* (pl)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - El mètode de Graham (Graham scan) és un mètode de càlcul computacional de l'envolupant convexa d'un grup finit de punts en el pla, amb una complexitat computacional O(n log n). El nom fa honor a , qui va publicar l'algorisme el 1972. L'algorisme calcula tots els vèrtexs de l'envolupant convexa ordenats al llarg de la frontera. Pot ser modificat fàcilment per trobar els punts que, sense ser vèrtexs, pertanyen a aquesta envolupant. (ca)
- Der Graham Scan (nach Ronald Graham 1972) ist ein effizienter Algorithmus zur Berechnung der konvexen Hülle einer endlichen Menge von Punkten in der Ebene. Bei Punkten liegt seine asymptotische Laufzeit in . (de)
- El método de Graham (Graham scan) es un método de cálculo computacional de la envolvente convexa de un conjunto finito de puntos en el plano, de complejidad O(nlogn). El nombre hace honor a Ronald Graham, quien publicó el algoritmo en 1972. El algoritmo calcula todos los vértices de la envolvente convexa ordenados a lo largo de la frontera. Puede ser fácilmente modificado para calcular los puntos que, sin ser vértices, pertenecen a dicha envolvente. (es)
- Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently. (en)
- En informatique, et en géométrie algorithmique, le parcours de Graham (aussi appelé algorithme de Graham) est un algorithme pour le calcul de l'enveloppe convexe d'un ensemble de points dans le plan. Son principal intérêt est sa complexité algorithmique en O(n log n) où n est le nombre de points. Cet algorithme doit son nom à Ronald Graham, qui a publié l'algorithme original en 1972. (fr)
- 그레이엄의 스캔(Graham Scan)은 평면상에서 유한한 점들의 볼록 껍질을 찾는 방법으로, 시간 복잡도는 O(n log n)이다. 이것의 이름은 로널드 그레이엄이 1972년 원시 알고리즘을 출판한 뒤에 붙여졌다. 이 알고리즘은 볼록껍질의 모든 정점들을 테두리를 따라 찾는다. 그이 알고리즘은 경계의 오목성을 효율적으로 감지하고 제거하기 위해 스택을 사용한다. (ko)
- Algorytm Grahama – efektywny algorytm wyszukiwania otoczki wypukłej skończonego zbioru punktów płaszczyzny; nie istnieją warianty dla przestrzeni o wyższych wymiarach. Pomysłodawcą algorytmu jest Ronald Graham. Czasowa złożoność obliczeniowa wynosi Algorytm przebiega następująco: 1.
* Wybierz punkt (ozn. O) o najniższej wartości współrzędnej y. 2.
* Przesuń wszystkie punkty tak, by punkt O pokrył się z początkiem układu współrzędnych. 3.
* Posortuj punkty leksykograficznie względem: 4.
* kąta pomiędzy wektorem a dodatnią osią układu współrzędnych, 5.
* odległości punktu od początku układu współrzędnych. 6.
* Wybierz punkt (ozn. S) o najmniejszej współrzędnej y; jeśli kilka punktów ma tę samą współrzędną y, wybierz spośród nich ten o najmniejszej współrzędnej x. 7.
* Przeglądaj listę posortowanych punktów poczynając od punktu S: 8.
* Od bieżącej pozycji weź trzy kolejne punkty (ozn. A, B, C). 9.
* Jeśli punkt B leży na zewnątrz trójkąta AOC, to może należeć do otoczki wypukłej. Przejdź do następnego punktu na liście. 10.
* Jeśli punkt B leży wewnątrz trójkąta AOC, to znaczy, że nie należy do otoczki. Usuń punkt B z listy i cofnij się o jedną pozycję (o ile bieżąca pozycja jest różna od początkowej). Ze względu na wcześniejsze kroki algorytmu (sortowanie i sposób wybierania analizowanych trójek punktów) dwa z trzech warunków należenia punktu B do trójkąta AOC są spełnione, tj. B leży po „wewnętrznej” względem trójkąta stronie prostych OA i OC. Zatem do stwierdzenia przynależności do trójkąta wystarczy zbadać, po której stronie odcinka AC znajduje się punkt B, w tym celu wykorzystuje się znak iloczynu wektorowego W praktyce można również utożsamić krok 4. z 1., tzn. przyjąć, że
* Przykładowy przebieg algorytmu
*
*
*
*
*
*
*
*
*
*
*
* (pl)
- Алгоритм Грэхема — алгоритм построения выпуклой оболочки в двумерном пространстве.В этом алгоритме задача о выпуклой оболочке решается с помощью стека, сформированного из точек-кандидатов. Все точки входного множества заносятся в стек, а потом точки, не являющиеся вершинами выпуклой оболочки, со временем удаляются из него. По завершении работы алгоритма в стеке остаются только вершины оболочки в порядке их обхода против часовой стрелки. (ru)
- O Exame de Graham, cuja denominação vem de Ronald Graham, é uma técnica de computação usada para determinar o envoltória convexa de um dado conjunto de pontos no plano como complexidade de tempo (n log n). (pt)
|
![[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)
