Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Closest_pair_of_points_problem> ?p ?o }
Showing triples 1 to 74 of
74
with 100 triples 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 in a space of dimension d 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 line-sweep-algorithms.
- Closest_pair_of_points_problem wikiPageID "9311111".
- Closest_pair_of_points_problem wikiPageLength "8173".
- Closest_pair_of_points_problem wikiPageOutDegree "34".
- Closest_pair_of_points_problem wikiPageRevisionID "695707409".
- Closest_pair_of_points_problem wikiPageWikiLink Analysis_of_algorithms.
- Closest_pair_of_points_problem wikiPageWikiLink Big_O_notation.
- Closest_pair_of_points_problem wikiPageWikiLink Brute-force_search.
- Closest_pair_of_points_problem wikiPageWikiLink Category:Articles_with_example_pseudocode.
- Closest_pair_of_points_problem wikiPageWikiLink Category:Geometric_algorithms.
- Closest_pair_of_points_problem wikiPageWikiLink Charles_E._Leiserson.
- Closest_pair_of_points_problem wikiPageWikiLink Clifford_Stein.
- Closest_pair_of_points_problem wikiPageWikiLink Computational_geometry.
- Closest_pair_of_points_problem wikiPageWikiLink Data_structure.
- Closest_pair_of_points_problem wikiPageWikiLink Decision_tree_model.
- Closest_pair_of_points_problem wikiPageWikiLink Delaunay_triangulation.
- Closest_pair_of_points_problem wikiPageWikiLink Divide_and_conquer_algorithms.
- Closest_pair_of_points_problem wikiPageWikiLink Dynamic_problem_(algorithms).
- Closest_pair_of_points_problem wikiPageWikiLink Element_distinctness_problem.
- Closest_pair_of_points_problem wikiPageWikiLink Euclidean_space.
- Closest_pair_of_points_problem wikiPageWikiLink Floor_and_ceiling_functions.
- Closest_pair_of_points_problem wikiPageWikiLink Geographic_information_system.
- Closest_pair_of_points_problem wikiPageWikiLink Introduction_to_Algorithms.
- Closest_pair_of_points_problem wikiPageWikiLink Lp_space.
- Closest_pair_of_points_problem wikiPageWikiLink Master_theorem.
- Closest_pair_of_points_problem wikiPageWikiLink Metric_space.
- Closest_pair_of_points_problem wikiPageWikiLink Minimum_bounding_box.
- Closest_pair_of_points_problem wikiPageWikiLink Model_of_computation.
- Closest_pair_of_points_problem wikiPageWikiLink Nearest_neighbor_search.
- Closest_pair_of_points_problem wikiPageWikiLink Recursion.
- Closest_pair_of_points_problem wikiPageWikiLink Ron_Rivest.
- Closest_pair_of_points_problem wikiPageWikiLink Set_(abstract_data_type).
- Closest_pair_of_points_problem wikiPageWikiLink Set_cover_problem.
- Closest_pair_of_points_problem wikiPageWikiLink Thomas_H._Cormen.
- Closest_pair_of_points_problem wikiPageWikiLink Voronoi_diagram.
- Closest_pair_of_points_problem wikiPageWikiLink File:Closest_pair.jpg.
- Closest_pair_of_points_problem wikiPageWikiLink File:Closest_pair_of_points.svg.
- Closest_pair_of_points_problem wikiPageWikiLinkText "Closest pair of points problem".
- Closest_pair_of_points_problem wikiPageWikiLinkText "bichromatic closest pair problem".
- Closest_pair_of_points_problem wikiPageWikiLinkText "closest pair of points problem".
- Closest_pair_of_points_problem wikiPageWikiLinkText "closest pair of vertices".
- Closest_pair_of_points_problem wikiPageWikiLinkText "closest pair problem".
- Closest_pair_of_points_problem wikiPageWikiLinkText "closest point search".
- Closest_pair_of_points_problem wikiPageUsesTemplate Template:=.
- Closest_pair_of_points_problem wikiPageUsesTemplate Template:Citation_needed.
- Closest_pair_of_points_problem wikiPageUsesTemplate Template:Cite_book.
- Closest_pair_of_points_problem wikiPageUsesTemplate Template:Math.
- Closest_pair_of_points_problem wikiPageUsesTemplate Template:Refbegin.
- Closest_pair_of_points_problem wikiPageUsesTemplate Template:Refend.
- Closest_pair_of_points_problem wikiPageUsesTemplate Template:Reflist.
- 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 hypernym Problem.
- Closest_pair_of_points_problem type Disease.
- Closest_pair_of_points_problem type Algorithm.
- 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 sameAs Q1209543.
- Closest_pair_of_points_problem sameAs Dichtestes_Punktpaar.
- Closest_pair_of_points_problem sameAs تعیین_نزدیکترین_زوج_نقاط_در_فضای_دو_بعدی.
- Closest_pair_of_points_problem sameAs 최근접_점쌍_문제.
- 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 Problem_najbližjega_para_točk.
- Closest_pair_of_points_problem sameAs Алгоритам_две_најближе_тачке.
- Closest_pair_of_points_problem sameAs ปัญหาการหาคู่ของจุดที่ใกล้กันที่สุด.
- Closest_pair_of_points_problem sameAs Q1209543.
- Closest_pair_of_points_problem wasDerivedFrom Closest_pair_of_points_problem?oldid=695707409.
- Closest_pair_of_points_problem depiction Closest_pair_of_points.svg.
- Closest_pair_of_points_problem isPrimaryTopicOf Closest_pair_of_points_problem.