Convex hull algorithms (original) (raw)
إن الخوارزميات التي تبني هياكلاً محدبة (convex hull) لها العديد من الاستخدامات الواسعة في الرياضيات وعلوم الحاسوب. في الهندسة الحسابية، تم اقتراح العديد من الخوارزميات لحساب الهيكل المحدب لمجموعة نقاط محددة، وكل خوارزمية من هذه الخوارزميات لها درجة مختلفة من تعقيد العمليات الحسابية. إن خوارزمية الهيكل المحدب تمثل الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة وواضحة ومن الممكن تقدير تعقيد هذه الخوارزميات ب n والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. أو من الممكن تقديرها ب h والتي تمثل عدد النقاط على حدود الهيكل المحدب. .
| Property | Value |
|---|---|
| dbo:abstract | إن الخوارزميات التي تبني هياكلاً محدبة (convex hull) لها العديد من الاستخدامات الواسعة في الرياضيات وعلوم الحاسوب. في الهندسة الحسابية، تم اقتراح العديد من الخوارزميات لحساب الهيكل المحدب لمجموعة نقاط محددة، وكل خوارزمية من هذه الخوارزميات لها درجة مختلفة من تعقيد العمليات الحسابية. إن خوارزمية الهيكل المحدب تمثل الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة وواضحة ومن الممكن تقدير تعقيد هذه الخوارزميات ب n والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. أو من الممكن تقديرها ب h والتي تمثل عدد النقاط على حدود الهيكل المحدب. . (ar) Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexities. Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and sometimes also in terms of h, the number of points on the convex hull. (en) En algorithmique géométrique, le calcul de l'enveloppe convexe est un problème algorithmique. Il consiste, étant donné un ensemble de points, à calculer leur enveloppe convexe. (fr) 볼록 껍질 알고리즘은 다양한 객체에 볼록 껍질을 만드는 알고리즘이다. 볼록 껍질 알고리즘은 수학 및 컴퓨터 과학에 광범위하게 적용되고 있다. 계산기하학에서, 유한한 점의 집합에 대해 볼록 껍질을 계산하는다양한 알고리즘들이 다양한 시간 복잡도로 제안되었다. 볼록 껍질을 계산하는 것은 모호하지 않으면서도 효율적으로 요구되는 볼록한 모양을 구성하는 것을 의미한다. 이러한 알고리즘의 복잡도는 주로 입력되는 점의 개수인 n 과, 간혹 볼록 껍질을 구성하는 점의 개수인 h 에 따라 비교된다. (ko) 凸包アルゴリズム（とつほうアルゴリズム）は、凸包を求めるアルゴリズムである。数学やコンピューターサイエンスで幅広い用途がある。 計算幾何学では、さまざまな計算複雑性を持つ、有限の点のセットの凸包を計算するためのアルゴリズムが考案されている。 凸包アルゴリズムの計算量は、通常は入力の点の数である n に依存し、また凸包上の点の数である h に依存することもある。 (ja) В вычислительной геометрии существует много алгоритмов нахождения выпуклой оболочки конечного множества точек с разной сложности вычислений. Область называется выпуклой, если отрезок, соединяющий произвольную пару ее точек, целиком лежит в этой области. Вычислить или построить выпуклую оболочку означает, что будет выполнено четкое и эффективное представление необходимой выпуклой формы. Вычислительная сложность соответствующих алгоритмов обычно рассчитывается в терминах n - число входных точек, и h - числа точек в выпуклой оболочке. (ru) В обчислювальній геометрії існує багато алгоритмів знаходження опуклої оболонки скінченної множини точок з різною складністю обчислень. Обчислити опуклу оболонку означає, що виконане недвозначне та ефективне представлення необхідної опуклої форми. Обчислювальна складність відповідних алгоритмів зазвичай розраховується в термінах n — числа вхідних точок, та h — числа точок в опуклій оболонці. (uk) |
| dbo:wikiPageExternalLink | https://archive.org/details/computationalgeo00berg http://wayback.vefsafn.is/wayback/20130721095350/http:/michal.is/projects/convex%2Dhull%2Dgift%2Dwrapping%2Dmethod/ http://www.cgal.org/Part/ConvexHullAlgorithms https://web.archive.org/web/20101127013711/http:/computacion.cs.cinvestav.mx/~anzures/geom/hull.html http://www.qhull.org/ |
| dbo:wikiPageID | 11700432 (xsd:integer) |
| dbo:wikiPageLength | 16451 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123252177 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quadrilateral dbr:Quicksort dbr:Ronald_Graham dbr:David_G._Kirkpatrick dbr:Decision_tree_model dbr:Dynamic_convex_hull dbr:Introduction_to_Algorithms dbr:Selim_Akl dbr:Thomas_H._Cormen dbr:Analysis_of_algorithms dbr:Mathematics dbr:Output-sensitive_algorithm dbr:Quickhull dbr:Clifford_Stein dbr:Convex_function dbr:Convex_hull dbr:Convex_polygon dbr:Convex_polytope dbr:Timothy_M._Chan dbr:Linear_time dbr:Stack_(abstract_data_type) dbr:Computational_geometry dbr:Computer_science dbr:Franco_P._Preparata dbr:Half-space_(geometry) dbr:Simple_polygon dbr:CGAL dbr:Data_structure dbr:Parabola dbr:Graham_scan dbr:Reduction_(complexity) dbr:Charles_E._Leiserson dbr:LP-type_problem dbr:Big_O_notation dbr:Convex_polyhedron dbr:Integer_sorting dbr:Orthogonal_convex_hull dbc:Convex_hull_algorithms dbr:Chan's_algorithm dbr:Kirkpatrick–Seidel_algorithm dbr:Sorting dbr:Face_(geometry) dbr:Gift_wrapping_algorithm dbr:Raimund_Seidel dbr:Springer-Verlag dbr:G._T._Toussaint dbr:Algebraic_decision_tree dbr:Ultimate_convex_hull_algorithm dbr:Ronald_L._Rivest dbr:Divide_and_conquer_(Convex_Hull) dbr:S.J._Hong dbr:Wikibooks:Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain |
| dbp:title | Convex Hull (en) |
| dbp:urlname | ConvexHull (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Harvtxt dbt:ISBN dbt:Main dbt:MathWorld dbt:Reflist dbt:Short_description dbt:Wikibooks |
| dcterms:subject | dbc:Convex_hull_algorithms |
| rdf:type | yago:WikicatConvexHullAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | إن الخوارزميات التي تبني هياكلاً محدبة (convex hull) لها العديد من الاستخدامات الواسعة في الرياضيات وعلوم الحاسوب. في الهندسة الحسابية، تم اقتراح العديد من الخوارزميات لحساب الهيكل المحدب لمجموعة نقاط محددة، وكل خوارزمية من هذه الخوارزميات لها درجة مختلفة من تعقيد العمليات الحسابية. إن خوارزمية الهيكل المحدب تمثل الشكل المطلوب لبناء الهيكل (convex hull) بطريقة فعالة وواضحة ومن الممكن تقدير تعقيد هذه الخوارزميات ب n والتي تمثل عدد النقاط المراد بناء الهيكل المحدب حولها. أو من الممكن تقديرها ب h والتي تمثل عدد النقاط على حدود الهيكل المحدب. . (ar) Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexities. Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and sometimes also in terms of h, the number of points on the convex hull. (en) En algorithmique géométrique, le calcul de l'enveloppe convexe est un problème algorithmique. Il consiste, étant donné un ensemble de points, à calculer leur enveloppe convexe. (fr) 볼록 껍질 알고리즘은 다양한 객체에 볼록 껍질을 만드는 알고리즘이다. 볼록 껍질 알고리즘은 수학 및 컴퓨터 과학에 광범위하게 적용되고 있다. 계산기하학에서, 유한한 점의 집합에 대해 볼록 껍질을 계산하는다양한 알고리즘들이 다양한 시간 복잡도로 제안되었다. 볼록 껍질을 계산하는 것은 모호하지 않으면서도 효율적으로 요구되는 볼록한 모양을 구성하는 것을 의미한다. 이러한 알고리즘의 복잡도는 주로 입력되는 점의 개수인 n 과, 간혹 볼록 껍질을 구성하는 점의 개수인 h 에 따라 비교된다. (ko) 凸包アルゴリズム（とつほうアルゴリズム）は、凸包を求めるアルゴリズムである。数学やコンピューターサイエンスで幅広い用途がある。 計算幾何学では、さまざまな計算複雑性を持つ、有限の点のセットの凸包を計算するためのアルゴリズムが考案されている。 凸包アルゴリズムの計算量は、通常は入力の点の数である n に依存し、また凸包上の点の数である h に依存することもある。 (ja) В вычислительной геометрии существует много алгоритмов нахождения выпуклой оболочки конечного множества точек с разной сложности вычислений. Область называется выпуклой, если отрезок, соединяющий произвольную пару ее точек, целиком лежит в этой области. Вычислить или построить выпуклую оболочку означает, что будет выполнено четкое и эффективное представление необходимой выпуклой формы. Вычислительная сложность соответствующих алгоритмов обычно рассчитывается в терминах n - число входных точек, и h - числа точек в выпуклой оболочке. (ru) В обчислювальній геометрії існує багато алгоритмів знаходження опуклої оболонки скінченної множини точок з різною складністю обчислень. Обчислити опуклу оболонку означає, що виконане недвозначне та ефективне представлення необхідної опуклої форми. Обчислювальна складність відповідних алгоритмів зазвичай розраховується в термінах n — числа вхідних точок, та h — числа точок в опуклій оболонці. (uk) |
| rdfs:label | Convex hull algorithms (en) خوارزمية الهيكل المحدب (ar) Calcul de l'enveloppe convexe (fr) 凸包アルゴリズム (ja) 볼록 껍질 알고리즘 (ko) Алгоритмы построения выпуклой оболочки (ru) Алгоритми обчислення опуклої оболонки (uk) |
| owl:sameAs | freebase:Convex hull algorithms yago-res:Convex hull algorithms wikidata:Convex hull algorithms dbpedia-ar:Convex hull algorithms dbpedia-fa:Convex hull algorithms dbpedia-fr:Convex hull algorithms dbpedia-ja:Convex hull algorithms dbpedia-ko:Convex hull algorithms dbpedia-ru:Convex hull algorithms dbpedia-uk:Convex hull algorithms https://global.dbpedia.org/id/4iMfp |
| prov:wasDerivedFrom | wikipedia-en:Convex_hull_algorithms?oldid=1123252177&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Convex_hull_algorithms |
| is dbo:wikiPageRedirects of | dbr:Convex_hull_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Bounding_volume dbr:Algorithmic_Geometry dbr:Delaunay_triangulation dbr:Convex_hull_algorithm dbr:Geometric_and_Topological_Inference dbr:Output-sensitive_algorithm dbr:Quickhull dbr:Convex_hull_of_a_simple_polygon dbr:Convex_polytope dbr:Godfried_Toussaint dbr:Graham_scan dbr:Point-set_triangulation dbr:Toussaint dbr:Polymake dbr:Chan's_algorithm dbr:Kirkpatrick–Seidel_algorithm dbr:Gift_wrapping_algorithm dbr:Vertex_enumeration_problem |
| is foaf:primaryTopic of | wikipedia-en:Convex_hull_algorithms |