This HTML5 document contains 114 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/
dbpedia-slhttp://sl.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n15http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
n21https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
n5http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
dbpedia-arhttp://ar.dbpedia.org/resource/
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbpedia-thhttp://th.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Minimum_distance
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Nearest_neighbor_search
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Area_(graph_drawing)
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:David_Mount
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Penny_graph
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Closest_pair_of_points_problem
rdf:type
yago:WikicatGeometricAlgorithms yago:Algorithm105847438 yago:WikicatSearchAlgorithms yago:PsychologicalFeature100023100 yago:Act100030358 yago:Activity100407535 yago:YagoPermanentlyLocatedEntity yago:Abstraction100002137 yago:Rule105846932 yago:Event100029378 dbo:Disease yago:Procedure101023820
rdfs:label
Recherche des deux points les plus rapprochés مسألة أقرب زوج من النقاط Closest pair of points problem Problema del par de puntos más cercanos Найближча пара точок Problema do par de pontos mais próximo Dichtestes Punktpaar Задача о паре ближайших точек 최근접 점쌍 문제
rdfs:comment
Задача о паре ближайших точек — это задача вычислительной геометрии. Дано n точек в метрическом пространстве, нужно найти пару точек с наименьшим расстоянием между ними. Задача о ближайших точках на евклидовой плоскости была одной из первых геометрических задач, которая подверглась систематическому изучению со стороны вычислительной сложности геометрических алгоритмов. 최근접 점쌍 문제 (closest pair problem)는 계산기하학의 문제로서, 거리 공간상에 n 개의 점이 주어졌을 때, 사이의 거리가 가장 짧은 두 점을 찾아내는 문제이다. 가능한 모든 점쌍들의 거리를 비교해 최솟값을 찾는 알고리즘은 O(n2)의 시간을 요구한다. 하지만 유클리드 공간이나 정해진 d의 차원을 가지는 Lp 공간에서는 O(n log n)의 시간에 해결 될 수 있다. 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.​​ Задача пошуку найближчої пари точок відноситься до задач обчислювальної геометрії: дано n точок в метричному просторі, знайти пару точок з найменшою відстанню між ними. Задача найближчої пари точок в евклідовій площині була однією з перших геометричних задач, яка вирішувалась на початку систематичного вивчення обчислювальної складності геометричних алгоритмів. 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. 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. 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. 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. مسألة أقرب زوج من النقاط (بالإنجليزية: Closest pair of points problem)‏ هي من أهم مسائل الهندسة الإحصائية. تهدف فكرتها إلى إيجاد أقرب نقطتين في مجموعة تحتوي س من النقاط في أقرب مسافة ممكنة. مسألة أقرب زوج من النقاط في مسافة إقليدية كانت من بين أولى المشاكل الهندسية التي تم علاجها في أصول الدراسة المنهجية من التعقيدالحسابي للخورزميات الهندسية. في النموذج الحسابي الذي يفترض أن دالتا الجزء الصحيح والسقف محسوب في وقت ثابت المسألة يمكن حلها في وقت (O(n log log n. إذا سمحنا التوزيع العشوائي لاستخدامها مع دالتا السقف يصبح حل المسألة في وقت (O(n
foaf:depiction
n5:Closest_pair_of_points.svg
dcterms:subject
dbc:Geometric_algorithms
dbo:wikiPageID
9311111
dbo:wikiPageRevisionID
1122843808
dbo:wikiPageWikiLink
dbr:Euclidean_space dbr:Approximation_ratio dbr:Set_(abstract_data_type) dbr:Metric_space dbr:Hash_table n15:Closest_pair_of_points.svg dbr:Analysis_of_algorithms dbr:Nearest_neighbor_search dbr:Asymptotic_analysis dbr:Linear_time dbr:Moore_neighborhood dbc:Geometric_algorithms dbr:Element_uniqueness_problem dbr:Richard_Lipton dbr:Data_structure dbr:Sweep_line_algorithm dbr:Random-access_machine dbr:Dynamic_problem_(algorithms) dbr:Computational_geometry dbr:Floor_function dbr:Divide-and-conquer_algorithm dbr:Bounding_box dbr:GIS dbr:Model_of_computation dbr:Algebraic_decision_tree dbr:Big_O_notation dbr:Expected_time
owl:sameAs
dbpedia-fa:تعیین_نزدیکترین_زوج_نقاط_در_فضای_دو_بعدی dbpedia-uk:Найближча_пара_точок dbpedia-sl:Problem_najbližjega_para_točk dbpedia-de:Dichtestes_Punktpaar dbpedia-th:ปัญหาการหาคู่ของจุดที่ใกล้กันที่สุด dbpedia-ko:최근접_점쌍_문제 n21:G64L dbpedia-fr:Recherche_des_deux_points_les_plus_rapprochés dbpedia-ru:Задача_о_паре_ближайших_точек dbpedia-pt:Problema_do_par_de_pontos_mais_próximo dbpedia-ar:مسألة_أقرب_زوج_من_النقاط dbpedia-sr:Алгоритам_две_најближе_тачке wikidata:Q1209543 dbpedia-es:Problema_del_par_de_puntos_más_cercanos yago-res:Closest_pair_of_points_problem freebase:m.028420v
dbp:wikiPageUsesTemplate
dbt:Harvtxt dbt:Reflist
dbo:thumbnail
n5:Closest_pair_of_points.svg?width=300
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. 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). 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. Задача пошуку найближчої пари точок відноситься до задач обчислювальної геометрії: дано n точок в метричному просторі, знайти пару точок з найменшою відстанню між ними. Задача найближчої пари точок в евклідовій площині була однією з перших геометричних задач, яка вирішувалась на початку систематичного вивчення обчислювальної складності геометричних алгоритмів. «Наївний» алгоритм полягає в знаходженні відстаней між усіма парами точок в просторі даної розмірності і виборі мінімальної, це вимагає часу. Виявляється, що ця проблема може бути вирішена за часу в Евклідовому просторі або просторі Lp фіксованої розмірності d. В алгебраїчному дереві рішень моделі обчислень, алгоритм складності є оптимальним. В обчислювальній моделі, яка передбачає, що функція знаходить результат за постійний час, кажуть, що проблема може бути вирішена за часу. Якщо допускається рандомізація, з використання функції підлоги, то проблема може бути вирішена за часу. 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).​​ مسألة أقرب زوج من النقاط (بالإنجليزية: Closest pair of points problem)‏ هي من أهم مسائل الهندسة الإحصائية. تهدف فكرتها إلى إيجاد أقرب نقطتين في مجموعة تحتوي س من النقاط في أقرب مسافة ممكنة. مسألة أقرب زوج من النقاط في مسافة إقليدية كانت من بين أولى المشاكل الهندسية التي تم علاجها في أصول الدراسة المنهجية من التعقيدالحسابي للخورزميات الهندسية. الخوارزمية الأكثر معرفة لإيجاد المسافة بين جميع أزواج النقاط في مساحة من البعد د واختيار الحد الأدنى تتطلب من الوقت (O(n log n في مسافة إقليدية في بعد ثابت د. في نموذج شجرة القرارات الجبرية الخوارزمية (O(n log n هي المثالية.المثالية يتبع من ملاحظتها أن مشكلة تفرد العنصر (مع الحد الأدنى ل (Ω(n log n) قابلة للاختزال لمسألة أقرب زوج من النقاط سواءٌ الحد الأدنى هو صفر بعد حل مسألة أقرب زوج من النقاط نستطيع الإجابة على سؤال عما إذا كان هنالك نوعان من نقاط متطابقة. في النموذج الحسابي الذي يفترض أن دالتا الجزء الصحيح والسقف محسوب في وقت ثابت المسألة يمكن حلها في وقت (O(n log log n. إذا سمحنا التوزيع العشوائي لاستخدامها مع دالتا السقف يصبح حل المسألة في وقت (O(n 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. Задача о паре ближайших точек — это задача вычислительной геометрии. Дано n точек в метрическом пространстве, нужно найти пару точек с наименьшим расстоянием между ними. Задача о ближайших точках на евклидовой плоскости была одной из первых геометрических задач, которая подверглась систематическому изучению со стороны вычислительной сложности геометрических алгоритмов. Наивный алгоритм нахождения расстояний между всеми парами в пространстве размерности d и выбора среди них наименьшего требует времени O(n2). Оказывается, что задача может быть решена за время в евклидовом пространстве или Lp пространстве фиксированной размерности d. В модели вычислений алгоритм со временем O(n log n) оптимален при сведении от .В вычислительной модели, в которой принимается, что вычисляема за постоянное время, задача может быть решена за время . Если мы позволяем применение рандомизации вместе с функцией floor, задача может быть решена за время O(n). 최근접 점쌍 문제 (closest pair problem)는 계산기하학의 문제로서, 거리 공간상에 n 개의 점이 주어졌을 때, 사이의 거리가 가장 짧은 두 점을 찾아내는 문제이다. 가능한 모든 점쌍들의 거리를 비교해 최솟값을 찾는 알고리즘은 O(n2)의 시간을 요구한다. 하지만 유클리드 공간이나 정해진 d의 차원을 가지는 Lp 공간에서는 O(n log n)의 시간에 해결 될 수 있다.
gold:hypernym
dbr:Problem
prov:wasDerivedFrom
wikipedia-en:Closest_pair_of_points_problem?oldid=1122843808&ns=0
dbo:wikiPageLength
8933
foaf:isPrimaryTopicOf
wikipedia-en:Closest_pair_of_points_problem
Subject Item
dbr:Divide-and-conquer_algorithm
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Euclidean_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:K-nearest_neighbors_algorithm
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Point-set_triangulation
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Greedy_geometric_spanner
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Rotating_calipers
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Straight_skeleton
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Closest_pair
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
dbo:wikiPageRedirects
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Closest_pair_of_points
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
dbo:wikiPageRedirects
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Closest_pair_problem
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
dbo:wikiPageRedirects
dbr:Closest_pair_of_points_problem
Subject Item
dbr:Closest_pairs_problem
dbo:wikiPageWikiLink
dbr:Closest_pair_of_points_problem
dbo:wikiPageRedirects
dbr:Closest_pair_of_points_problem
Subject Item
wikipedia-en:Closest_pair_of_points_problem
foaf:primaryTopic
dbr:Closest_pair_of_points_problem