Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Closest_pair_of_points_problem> ?p ?o. }
Showing items 1 to 33 of
33
with 100 items per page.
- Closest_pair_of_points_problem abstract "The closest pair of points problem or closest pair problem is a problem of computational geometry: given n 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 which were treated at the origins of the systematic study of the computational complexity of geometric algorithms.A naive algorithm of finding distances between all pairs of points and selecting the minimum requires O(dn2) time. It turns out that the problem may be solved in O(n log n) time in a Euclidean space or Lp space of fixed dimension d. In the algebraic decision tree model of computation, the O(n log n) algorithm is optimal. The optimality follows from the observation that the element uniqueness problem (with the lower bound of Ω(n log n) for time complexity) is reducible to the closest pair problem: checking whether the minimal distance is 0 after the solving of the closest pair problem answers the question whether there are two coinciding points.In the computational model which assumes that the floor function is computable in constant time the problem can be solved in O(n log log n) time. If we allow randomization to be used together with the floor function, the problem can be solved in O(n) time.".
- Closest_pair_of_points_problem thumbnail Closest_pair_of_points.svg?width=300.
- Closest_pair_of_points_problem wikiPageExternalLink Closest-pair_problem.
- Closest_pair_of_points_problem wikiPageExternalLink ClosestPair.pdf.
- Closest_pair_of_points_problem wikiPageExternalLink tc?module=Static&d1=tutorials&d2=lineSweep.
- Closest_pair_of_points_problem wikiPageID "9311111".
- Closest_pair_of_points_problem wikiPageRevisionID "586313533".
- Closest_pair_of_points_problem hasPhotoCollection Closest_pair_of_points_problem.
- Closest_pair_of_points_problem subject Category:Articles_with_example_pseudocode.
- Closest_pair_of_points_problem subject Category:Geometric_algorithms.
- Closest_pair_of_points_problem type Abstraction100002137.
- Closest_pair_of_points_problem type Act100030358.
- Closest_pair_of_points_problem type Activity100407535.
- Closest_pair_of_points_problem type Algorithm105847438.
- Closest_pair_of_points_problem type Event100029378.
- Closest_pair_of_points_problem type GeometricAlgorithms.
- Closest_pair_of_points_problem type Procedure101023820.
- Closest_pair_of_points_problem type PsychologicalFeature100023100.
- Closest_pair_of_points_problem type Rule105846932.
- Closest_pair_of_points_problem type YagoPermanentlyLocatedEntity.
- Closest_pair_of_points_problem comment "The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them.".
- Closest_pair_of_points_problem label "Closest pair of points problem".
- Closest_pair_of_points_problem label "Dichtestes Punktpaar".
- Closest_pair_of_points_problem label "Problema do par de pontos mais próximo".
- Closest_pair_of_points_problem sameAs Dichtestes_Punktpaar.
- Closest_pair_of_points_problem sameAs Problema_do_par_de_pontos_mais_próximo.
- Closest_pair_of_points_problem sameAs m.028420v.
- Closest_pair_of_points_problem sameAs Q1209543.
- Closest_pair_of_points_problem sameAs Q1209543.
- Closest_pair_of_points_problem sameAs Closest_pair_of_points_problem.
- Closest_pair_of_points_problem wasDerivedFrom Closest_pair_of_points_problem?oldid=586313533.
- Closest_pair_of_points_problem depiction Closest_pair_of_points.svg.
- Closest_pair_of_points_problem isPrimaryTopicOf Closest_pair_of_points_problem.
