2-dimensional space, Euclidean metric: Difference between revisions

Revision as of 07:52, 10 April 2023

Given $n$ points in 2-dimensional space equipped with the Eucildean metric, find a pair of points with the smallest distance between them.

$n$: number of points

$k$: dimension of space

Name	Year	Time	Space	Approximation Factor	Model	Reference
Khuller; Matias	1995	$O(n)$	$O(n)$, not sure if this is auxiliary	Exact	Randomized	Time & Space
Shamos; Hoey	1975	$O(n \log n)$	$O(n)$	Exact	Deterministic	Time

Error creating thumbnail: Unable to save thumbnail to destination

Error creating thumbnail: Unable to save thumbnail to destination

Error creating thumbnail: Unable to save thumbnail to destination

@@ Line 10: / Line 10: @@
 == Parameters ==
-No parameters found.
+$n$: number of points
+$k$: dimension of space
 == Table of Algorithms ==
@@ Line 20: / Line 22: @@
 |-
-| [[Khuller; Matias Randomized Sieve ( Closest Pair Problem)|Khuller; Matias Randomized Sieve]] || 1995 || $O(n)$ || $O(n)$, not sure if this is auxiliary || Exact || Randomized || [https://dl.acm.org/citation.cfm?id=207181 Time] & [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/S0890540185710498, Space]
+| [[Khuller; Matias ( Closest Pair Problem)|Khuller; Matias]] || 1995 || $O(n)$ || $O(n)$, not sure if this is auxiliary || Exact || Randomized || [https://www.sciencedirect.com/science/article/pii/S0890540185710498 Time] & [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/S0890540185710498, Space]
 |-
-| [[Shamos; Hoey (2-dimensional space, Euclidean metric Closest Pair Problem)|Shamos; Hoey]] || 1975 || $O(n logn)$ || $O(n)$ || Exact || Deterministic || [https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/document/4567872 Time]
+| [[Shamos; Hoey (2-dimensional space, Euclidean metric Closest Pair Problem)|Shamos; Hoey]] || 1975 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || [https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/document/4567872 Time]
 |-
 |}