| dbo:abstract
|
- Das Problem des dichtesten Punktpaares (englisch closest pair of points problem) ist die Suche nach den zwei am dichtesten beieinander liegenden Punkten in einer Ebene. Gegeben ist eine beliebige Menge von Punkten in der Ebene und gesucht sind zwei dieser Punkte, sodass der euklidische Abstand minimal ist. Ein ähnliches Problem ist die Suche nach den zwei am weitesten voneinander entfernten Punkten in der Ebene, also den zwei Punkten mit dem maximalen euklidischen Abstand. (de)
- مسألة أقرب زوج من النقاط (بالإنجليزية: Closest pair of points problem) هي من أهم مسائل الهندسة الإحصائية. تهدف فكرتها إلى إيجاد أقرب نقطتين في مجموعة تحتوي س من النقاط في أقرب مسافة ممكنة. مسألة أقرب زوج من النقاط في مسافة إقليدية كانت من بين أولى المشاكل الهندسية التي تم علاجها في أصول الدراسة المنهجية من التعقيدالحسابي للخورزميات الهندسية. الخوارزمية الأكثر معرفة لإيجاد المسافة بين جميع أزواج النقاط في مساحة من البعد د واختيار الحد الأدنى تتطلب من الوقت (O(n log n في مسافة إقليدية في بعد ثابت د. في نموذج شجرة القرارات الجبرية الخوارزمية (O(n log n هي المثالية.المثالية يتبع من ملاحظتها أن مشكلة تفرد العنصر (مع الحد الأدنى ل (Ω(n log n) قابلة للاختزال لمسألة أقرب زوج من النقاط سواءٌ الحد الأدنى هو صفر بعد حل مسألة أقرب زوج من النقاط نستطيع الإجابة على سؤال عما إذا كان هنالك نوعان من نقاط متطابقة. في النموذج الحسابي الذي يفترض أن دالتا الجزء الصحيح والسقف محسوب في وقت ثابت المسألة يمكن حلها في وقت (O(n log log n. إذا سمحنا التوزيع العشوائي لاستخدامها مع دالتا السقف يصبح حل المسألة في وقت (O(n (ar)
- The closest pair of points problem or closest pair problem is a problem of computational geometry: given points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane was among the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms. (en)
- En geometría computacional, el problema del par de puntos más cercano es un problema clásico donde "Dados n puntos en un espacio métrico, se pide encontrar un par de puntos con la distancia más pequeña entre ellos". El problema del par de puntos más cercano en el plano euclídeo fue de los primeros problemas tratados en el estudio sistemático de la complejidad computacional de algoritmos geométricos. Un algoritmo ingenuo para resolver el problema consiste en "calcular las distancias entre todos los pares de puntos del conjunto y seleccionar el mínimo", que requiere un tiempo O(n^2). Pero resulta que el problema puede ser solucionado en tiempo O(n log n) en un espacio euclídeo. Este tiempo puede incluso ser mejorado: Si se asume que la función de parte entera (floor) es computable en tiempo constante, el problema puede ser solucionado en tiempo O(n log log n). Si además se permite utilizar aleatorización, el problema puede ser solucionado en tiempo O(n). (es)
- En géométrie algorithmique, la recherche des deux points les plus rapprochés est le problème qui consiste à trouver une paire de points d'un ensemble fini de points dans un espace métrique dont la distance est minimale. Il fait partie des problèmes fondateurs de la géométrie algorithmique. (fr)
- 최근접 점쌍 문제 (closest pair problem)는 계산기하학의 문제로서, 거리 공간상에 n 개의 점이 주어졌을 때, 사이의 거리가 가장 짧은 두 점을 찾아내는 문제이다. 가능한 모든 점쌍들의 거리를 비교해 최솟값을 찾는 알고리즘은 O(n2)의 시간을 요구한다. 하지만 유클리드 공간이나 정해진 d의 차원을 가지는 Lp 공간에서는 O(n log n)의 시간에 해결 될 수 있다. (ko)
- O problema do par de pontos mais próximo consiste em, dado um conjunto de n pontos num espaço métrico, encontrar os dois pontos do conjunto que possuem a menor distância um do outro. A versão em duas dimensões, para pontos num plano, estava entre os primeiros problemas geométricos que foram tratados na origem do estudo de complexidade computacional de algoritmos geométricos. Se forem computadas as distâncias entre todos os pares de pontos do conjunto, há n(n-1)/2 computações antes de ser possível decidir inequivocamente qual o par que apresenta a menor distância. Esse algoritmo é conhecido como força bruta e tem complexidade de tempo O(n2), ou seja, seu tempo de execução é proporcional ao quadrado do número de pontos do conjunto considerado. Porém, pesquisadores em geometria computacional descobriram que este problema pode ser resolvido em tempo O(n log n) em um espaço euclidiano ou espaço Lp de dimensão d fixa. No modelo computacional que assume que a função chão é computada em tempo constante, o problema pode ser resolvido em tempo de O(n log log n). Se for permitido o uso de escolhas aleatórias em conjunto com a função chão, o problema pode ser resolvido em tempo O(n). (pt)
- Задача о паре ближайших точек — это задача вычислительной геометрии. Дано n точек в метрическом пространстве, нужно найти пару точек с наименьшим расстоянием между ними. Задача о ближайших точках на евклидовой плоскости была одной из первых геометрических задач, которая подверглась систематическому изучению со стороны вычислительной сложности геометрических алгоритмов. Наивный алгоритм нахождения расстояний между всеми парами в пространстве размерности d и выбора среди них наименьшего требует времени O(n2). Оказывается, что задача может быть решена за время в евклидовом пространстве или Lp пространстве фиксированной размерности d. В модели вычислений алгоритм со временем O(n log n) оптимален при сведении от .В вычислительной модели, в которой принимается, что вычисляема за постоянное время, задача может быть решена за время . Если мы позволяем применение рандомизации вместе с функцией floor, задача может быть решена за время O(n). (ru)
- Задача пошуку найближчої пари точок відноситься до задач обчислювальної геометрії: дано n точок в метричному просторі, знайти пару точок з найменшою відстанню між ними. Задача найближчої пари точок в евклідовій площині була однією з перших геометричних задач, яка вирішувалась на початку систематичного вивчення обчислювальної складності геометричних алгоритмів. «Наївний» алгоритм полягає в знаходженні відстаней між усіма парами точок в просторі даної розмірності і виборі мінімальної, це вимагає часу. Виявляється, що ця проблема може бути вирішена за часу в Евклідовому просторі або просторі Lp фіксованої розмірності d. В алгебраїчному дереві рішень моделі обчислень, алгоритм складності є оптимальним. В обчислювальній моделі, яка передбачає, що функція знаходить результат за постійний час, кажуть, що проблема може бути вирішена за часу. Якщо допускається рандомізація, з використання функції підлоги, то проблема може бути вирішена за часу. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8933 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Das Problem des dichtesten Punktpaares (englisch closest pair of points problem) ist die Suche nach den zwei am dichtesten beieinander liegenden Punkten in einer Ebene. Gegeben ist eine beliebige Menge von Punkten in der Ebene und gesucht sind zwei dieser Punkte, sodass der euklidische Abstand minimal ist. Ein ähnliches Problem ist die Suche nach den zwei am weitesten voneinander entfernten Punkten in der Ebene, also den zwei Punkten mit dem maximalen euklidischen Abstand. (de)
- The closest pair of points problem or closest pair problem is a problem of computational geometry: given points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane was among the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms. (en)
- En géométrie algorithmique, la recherche des deux points les plus rapprochés est le problème qui consiste à trouver une paire de points d'un ensemble fini de points dans un espace métrique dont la distance est minimale. Il fait partie des problèmes fondateurs de la géométrie algorithmique. (fr)
- 최근접 점쌍 문제 (closest pair problem)는 계산기하학의 문제로서, 거리 공간상에 n 개의 점이 주어졌을 때, 사이의 거리가 가장 짧은 두 점을 찾아내는 문제이다. 가능한 모든 점쌍들의 거리를 비교해 최솟값을 찾는 알고리즘은 O(n2)의 시간을 요구한다. 하지만 유클리드 공간이나 정해진 d의 차원을 가지는 Lp 공간에서는 O(n log n)의 시간에 해결 될 수 있다. (ko)
- مسألة أقرب زوج من النقاط (بالإنجليزية: Closest pair of points problem) هي من أهم مسائل الهندسة الإحصائية. تهدف فكرتها إلى إيجاد أقرب نقطتين في مجموعة تحتوي س من النقاط في أقرب مسافة ممكنة. مسألة أقرب زوج من النقاط في مسافة إقليدية كانت من بين أولى المشاكل الهندسية التي تم علاجها في أصول الدراسة المنهجية من التعقيدالحسابي للخورزميات الهندسية. في النموذج الحسابي الذي يفترض أن دالتا الجزء الصحيح والسقف محسوب في وقت ثابت المسألة يمكن حلها في وقت (O(n log log n. إذا سمحنا التوزيع العشوائي لاستخدامها مع دالتا السقف يصبح حل المسألة في وقت (O(n (ar)
- En geometría computacional, el problema del par de puntos más cercano es un problema clásico donde "Dados n puntos en un espacio métrico, se pide encontrar un par de puntos con la distancia más pequeña entre ellos". El problema del par de puntos más cercano en el plano euclídeo fue de los primeros problemas tratados en el estudio sistemático de la complejidad computacional de algoritmos geométricos. (es)
- O problema do par de pontos mais próximo consiste em, dado um conjunto de n pontos num espaço métrico, encontrar os dois pontos do conjunto que possuem a menor distância um do outro. A versão em duas dimensões, para pontos num plano, estava entre os primeiros problemas geométricos que foram tratados na origem do estudo de complexidade computacional de algoritmos geométricos. (pt)
- Задача пошуку найближчої пари точок відноситься до задач обчислювальної геометрії: дано n точок в метричному просторі, знайти пару точок з найменшою відстанню між ними. Задача найближчої пари точок в евклідовій площині була однією з перших геометричних задач, яка вирішувалась на початку систематичного вивчення обчислювальної складності геометричних алгоритмів. (uk)
- Задача о паре ближайших точек — это задача вычислительной геометрии. Дано n точек в метрическом пространстве, нужно найти пару точек с наименьшим расстоянием между ними. Задача о ближайших точках на евклидовой плоскости была одной из первых геометрических задач, которая подверглась систематическому изучению со стороны вычислительной сложности геометрических алгоритмов. (ru)
|
| rdfs:label
|
- مسألة أقرب زوج من النقاط (ar)
- Dichtestes Punktpaar (de)
- Problema del par de puntos más cercanos (es)
- Closest pair of points problem (en)
- Recherche des deux points les plus rapprochés (fr)
- 최근접 점쌍 문제 (ko)
- Задача о паре ближайших точек (ru)
- Problema do par de pontos mais próximo (pt)
- Найближча пара точок (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
