| dbo:abstract | - En geometria computacional, l'algorisme de l'embolcallament (de l'anglès Gift wrapping algorithm) és un algorisme per calcular l'envolupant convexa d'un sistema finit de punts. Tal com el nom suggereix, la idea principal de l'algorisme és embolcallar el conjunt de punts com si es tractés d'un paper de regal, definint-lo a partir d'un punt i estirant-lo i girant-lo al voltant del núvol de punts fins a ternir-los tots recoberts. Tot i que es pot generalitzar a 3 dimensions o més, l'algorisme va ser inicialment descrit per ser aplicat en 2 dimensions sobre un pla; en aquest cas també rep el nom de Jarvis march, en honor de , qui va publicar l'algorisme el 1973. L'algorisme no és gaire eficient; té un temps de processament O(nh) on n és el nombre total de punts i h la mida de l'envolupant. És per aquest motiu que posteriorment han sortit altres algorismes com el mètode de Graham o l', que partint d'una idea similar utilitzen diversos trucs per augmentar l'eficiència. (ca)
- Der Gift-Wrapping-Algorithmus, auch Jarvis-March genannt, ist ein Algorithmus zur Berechnung der konvexen Hülle einer Punktemenge im zweidimensionalen Raum. Er wurde 1973 von R. A. Jarvis veröffentlicht. Der Algorithmus gehört zu den „ausgabesensitiven“ (englisch output-sensitive) Algorithmen. (de)
- In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points. (en)
- En géométrie algorithmique, la marche de Jarvis est un algorithme pour calculer l'enveloppe convexe d'un ensemble fini de points. L'idée de l'algorithme est d' « envelopper » l'ensemble de points dans un « papier cadeau » : on accroche ce papier à l'un des points, on le tend, puis on tourne autour du nuage de point. (fr)
- 계산기하학에서 선물 포장 알고리즘은 주어진 점들의 집합에서 볼록 껍질을 계산하는 알고리즘이다. (ko)
- ギフト包装法（英: Gift wrapping algorithm）やJarvisの行進法（英: Jarvis's march）とは、計算幾何学における点の集合の凸包を求めるアルゴリズム。 (ja)
- Algorytm Jarvisa, marsz Jarvisa lub owijanie prezentów (ang. gift wrapping algorithm) – metoda wyznaczania otoczki wypukłej zbioru punktów umieszczonych na płaszczyźnie lub przestrzeni o większej liczbie wymiarów. Algorytm został niezależnie opracowany przez Donalda Chanda oraz Shama Kapura (1970) oraz R. Jarvisa (1973, przypadek na płaszczyźnie). (pl)
- O algoritmo de embrulho para presente ou do embrulho de presentes (gift wrapping) é um algoritmo que serve para encontrar o fecho convexo de um conjunto de pontos em dimensões arbitrárias. Trata-se de uma generalização do , desenvolvida por Chand e Kapur. (pt)
- Алгоритм Джарвиса (или алгоритм обхода Джарвиса, или алгоритм заворачивания подарка) определяет последовательность элементов множества, образующих выпуклую оболочку для этого множества. Метод можно представить как обтягивание верёвкой множества вбитых в доску гвоздей. Алгоритм работает за время , где — общее число точек на плоскости, — число точек в выпуклой оболочке. (ru)
- Алгоритм Джарвіса (або алгоритм загортання подарунка) — алгоритм знаходження опуклої оболонки. Часова складність — О(n * h), де n — кількість точок, h — кількість точок опуклої оболонки. Тобто, алгоритм найбільш ефективний у випадку малої кількості точок опуклої оболонки. (uk)
|
| dbo:thumbnail | |
| dbo:wikiPageID | |
| dbo:wikiPageLength | - 4967 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID | |
| dbo:wikiPageWikiLink | |
| dbp:wikiPageUsesTemplate | |
| dcterms:subject | |
| gold:hypernym | |
| rdf:type | |
| rdfs:comment | - Der Gift-Wrapping-Algorithmus, auch Jarvis-March genannt, ist ein Algorithmus zur Berechnung der konvexen Hülle einer Punktemenge im zweidimensionalen Raum. Er wurde 1973 von R. A. Jarvis veröffentlicht. Der Algorithmus gehört zu den „ausgabesensitiven“ (englisch output-sensitive) Algorithmen. (de)
- In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points. (en)
- En géométrie algorithmique, la marche de Jarvis est un algorithme pour calculer l'enveloppe convexe d'un ensemble fini de points. L'idée de l'algorithme est d' « envelopper » l'ensemble de points dans un « papier cadeau » : on accroche ce papier à l'un des points, on le tend, puis on tourne autour du nuage de point. (fr)
- 계산기하학에서 선물 포장 알고리즘은 주어진 점들의 집합에서 볼록 껍질을 계산하는 알고리즘이다. (ko)
- ギフト包装法（英: Gift wrapping algorithm）やJarvisの行進法（英: Jarvis's march）とは、計算幾何学における点の集合の凸包を求めるアルゴリズム。 (ja)
- Algorytm Jarvisa, marsz Jarvisa lub owijanie prezentów (ang. gift wrapping algorithm) – metoda wyznaczania otoczki wypukłej zbioru punktów umieszczonych na płaszczyźnie lub przestrzeni o większej liczbie wymiarów. Algorytm został niezależnie opracowany przez Donalda Chanda oraz Shama Kapura (1970) oraz R. Jarvisa (1973, przypadek na płaszczyźnie). (pl)
- O algoritmo de embrulho para presente ou do embrulho de presentes (gift wrapping) é um algoritmo que serve para encontrar o fecho convexo de um conjunto de pontos em dimensões arbitrárias. Trata-se de uma generalização do , desenvolvida por Chand e Kapur. (pt)
- Алгоритм Джарвиса (или алгоритм обхода Джарвиса, или алгоритм заворачивания подарка) определяет последовательность элементов множества, образующих выпуклую оболочку для этого множества. Метод можно представить как обтягивание верёвкой множества вбитых в доску гвоздей. Алгоритм работает за время , где — общее число точек на плоскости, — число точек в выпуклой оболочке. (ru)
- Алгоритм Джарвіса (або алгоритм загортання подарунка) — алгоритм знаходження опуклої оболонки. Часова складність — О(n * h), де n — кількість точок, h — кількість точок опуклої оболонки. Тобто, алгоритм найбільш ефективний у випадку малої кількості точок опуклої оболонки. (uk)
- En geometria computacional, l'algorisme de l'embolcallament (de l'anglès Gift wrapping algorithm) és un algorisme per calcular l'envolupant convexa d'un sistema finit de punts. Tal com el nom suggereix, la idea principal de l'algorisme és embolcallar el conjunt de punts com si es tractés d'un paper de regal, definint-lo a partir d'un punt i estirant-lo i girant-lo al voltant del núvol de punts fins a ternir-los tots recoberts. (ca)
|
| rdfs:label | - Algorisme de l'embolcallament (ca)
- Gift-Wrapping-Algorithmus (de)
- Gift wrapping algorithm (en)
- Marche de Jarvis (fr)
- 선물 포장 알고리즘 (ko)
- ギフト包装法 (ja)
- Algorytm Jarvisa (pl)
- Algoritmo embrulho para presente (pt)
- Алгоритм Джарвиса (ru)
- Алгоритм Джарвіса (uk)
|
| owl:sameAs | |
| prov:wasDerivedFrom | |
| foaf:depiction | |
| foaf:isPrimaryTopicOf | |
| isdbo:wikiPageRedirects of | |
| isdbo:wikiPageWikiLink of | |
| isfoaf:primaryTopic of | |
