New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:35, 15 February 2023 EKF SLAM (SLAM Algorithms SLAM Algorithms) (hist | edit) [417 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == http://ais.informatik.uni-freiburg.de/teaching/ss12/robotics/slides/12-slam.pdf")
- 10:35, 15 February 2023 Image quilting Efros-Freeman (Texture Synthesis Texture Synthesis) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://dl.acm.org/doi/abs/10.1145/383259.383296")
- 10:35, 15 February 2023 R. Paget ; I.D. Longstaff (Texture Synthesis Texture Synthesis) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://ieeexplore.ieee.org/abstract/document/679446")
- 10:35, 15 February 2023 Image analogies Hertzmann (Texture Synthesis Texture Synthesis) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N log n)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://dl.acm.org/doi/abs/10.1145/383259.383295")
- 10:35, 15 February 2023 Non-parametric sampling Efros and Leung (Texture Synthesis Texture Synthesis) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/abstract/document/790383")
- 10:35, 15 February 2023 Petro Vlahos Algorithm (Image Compositing Image Compositing) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k/r)$ == Space Complexity == $O(nk)$?? words (Keeps track of all pixels across all images) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1985 == Reference ==")
- 10:35, 15 February 2023 Roth AlignACE (Motif Search Motif Search) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ words (derived: essentially just modified Gibbs sampling) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9788350")
- 10:35, 15 February 2023 Alon; Moshkovitz & Safra (Unweighted Set-Covering The Set-Covering Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://dl.acm.org/doi/pdf/10.1145/1150334.1150336")
- 10:35, 15 February 2023 Chvatal greedy heuristic (Weighted Set-Covering The Set-Covering Problem) (hist | edit) [455 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(dn^{2})$ == Space Complexity == $O(dm)$ (Derived -- worst case, updating each set in S to be something else and we don't want to change the input) == Description == == Approximate? == Approximate Approximation Factor: ln n - lnln n + \Theta(1) == Randomized? == No, deterministic == Model of Computation == == Year == 1979 == Reference == https://www.jstor.org/stable/3689577#metadata_info_tab_contents")
- 10:35, 15 February 2023 The SUSAN corner detector ( Corner Detection) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference ==")
- 10:35, 15 February 2023 L. Kitchen and A. Rosenfeld (Grey-scale Corner Detection) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1982 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0167865582900204")
- 10:34, 15 February 2023 Harris and Stephens algorithm ( Corner Detection) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1988 == Reference == http://www.bmva.org/bmvc/1988/avc-88-023.pdf")
- 10:34, 15 February 2023 Barvinok (Geometric Maximum TSP The Traveling-Salesman Problem) (hist | edit) [415 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} loglogE)$ == Space Complexity == $O(V)$? memory cells (Derived: One memory cell per tunnel-city pair, with one tunnel total) == Description == Tunneling == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/876638.876640")
- 10:34, 15 February 2023 Dantzig-Fulkerson-Johnson (DFJ) formulation (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.674}^V E^{2})$ == Space Complexity == $O({2}^V)$ words (http://web.ist.utl.pt/~ist11038/CD_Casquilho/TSP1992EJOR_Laporte.pdf) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1954 == Reference == https://doi.org/10.1287/opre.2.4.393")
- 10:34, 15 February 2023 Miller-Tucker-Zemlin (MTZ) formulation (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $exp(V)$ == Space Complexity == $O(V^{4})$ words (Derived: V^2 + 2V constraints on V^2 variables, most integer programs use space of O(nm) where n=#vars and m=#constraints) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/doi/10.1145/321043.321046")
- 10:34, 15 February 2023 Micali and Vazirani ( Maximum Cardinality Matching) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(V)$ not mentioned (https://link.springer.com/content/pdf/10.1007/PL00009186.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Restricted Randomness (RR) == Year == 1980 == Reference == https://dl.acm.org/doi/10.1109/SFCS.1980.12")
- 10:34, 15 February 2023 Brélaz (DSatur) (3-Graph Coloring Graph Coloring) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V + E)$ words (Derived using adjacency lists) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://dl.acm.org/doi/10.1145/359094.359101")
- 10:34, 15 February 2023 Karger, Blum ( Graph Coloring) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(poly(V))$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: $\tilde{O}(n^{3/14})$ == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4204")
- 10:34, 15 February 2023 Schonhage's algorithm (Matrix Multiplication Matrix Product) (hist | edit) [437 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{({3}*log52/log110)}) ~ O(n^{2.{521}8})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/abs/10.1137/0210032")
- 10:34, 15 February 2023 Bini's algorithm (Matrix Multiplication Matrix Product) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.{779}9})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: $O(n logn)$ error == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://doi.org/10.1016/0020-0190(79)90113-3")
- 10:34, 15 February 2023 Chin (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: There are a few auxiliary variables, only one of which is variable length. That is a list of length $O(n)$.) == Description == == Approximate? == Approximate Approximation Factor: 1.2485 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://dl.acm.org/citation.cfm?id=359556")
- 10:34, 15 February 2023 Chandra (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [502 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Derived: cannot find pdf of original paper or any description of the actual algorithm, but likely the same space as Chin's algorithm) == Description == == Approximate? == Approximate Approximation Factor: 2 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.worldcat.org/title/computing-matrix-chain-products-in-near-...")
- 10:34, 15 February 2023 Czumaj (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [523 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(\log n)$ == Space Complexity == $O(n)$ words? (Derived: solving the optimal triangulation problem of a convex polygon where there are $n+1$ vertices and $n+1$, so total $O(n)$ auxiliary space) == Description == == Approximate? == Approximate Approximation Factor: 1.1547 == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1996 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?d...")
- 10:34, 15 February 2023 Dynamic Programming (Change-Making Problem Change-Making Problem) (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(Sn)$ == Space Complexity == $O(Sn)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == https://dl.acm.org/doi/10.1145/321864.321874")
- 10:34, 15 February 2023 Brute Force (Change-Making Problem Change-Making Problem) (hist | edit) [258 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(S^n)$ == Space Complexity == $O(n)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 10:34, 15 February 2023 Dynamic Programming (Rod-Cutting Problem Rod-Cutting Problem) (hist | edit) [255 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 10:34, 15 February 2023 Brute Force (Rod-Cutting Problem Rod-Cutting Problem) (hist | edit) [257 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 10:34, 15 February 2023 PMS (Motif Search Motif Search) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm^{2} \sigma)$ == Space Complexity == $O(m^{2} n)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://ieeexplore.ieee.org/abstract/document/4359890")
- 10:34, 15 February 2023 Risotto (Motif Search Motif Search) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2} \sigma)$ == Space Complexity == $O(mn^{2})$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://link.springer.com/chapter/10.1007/11682462_69")
- 10:34, 15 February 2023 Census (Motif Search Motif Search) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k nm \sigma)$ == Space Complexity == $O(mnk)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-45078-8_5")
- 10:34, 15 February 2023 Mitra (Motif Search Motif Search) (hist | edit) [372 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k nm \sigma)$ == Space Complexity == $O(mnk)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://pubmed.ncbi.nlm.nih.gov/12169566/")
- 10:34, 15 February 2023 Speller (Motif Search Motif Search) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2} \sigma)$ == Space Complexity == $O(mn^{2}/w)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/chapter/10.1007/BFb0054337")
- 10:34, 15 February 2023 Perumalla and Deo (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O(n)$ auxiliary words (constant number of arrays as outlined in algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.1291&rep=rep1&type=pdf")
- 10:34, 15 February 2023 Kadane's Algorithm (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [301 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (keep track of current tail sum and best sum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1982 == Reference == -")
- 10:34, 15 February 2023 Shamos (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [290 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(log n)$ auxiliary words (keep track of recursive maximums) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == -")
- 10:34, 15 February 2023 Faster Brute Force (via x(L:U) = x(L:U-1)+x(U)) (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [373 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://dl.acm.org/doi/pdf/10.1145/358234.381162")
- 10:34, 15 February 2023 Grenander (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [285 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (storing precomputed cumulative sums) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == -")
- 10:34, 15 February 2023 Brute Force (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == -")
- 10:34, 15 February 2023 Bringman (Subset Sum The Subset-Sum Problem) (hist | edit) [395 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(nt^{1+\epsilon})$ == Space Complexity == \tilde{O}(nt^\epsilon) (https://arxiv.org/abs/1610.04712) == Description == == Approximate? == Approximate Approximation Factor: (n+t)^{-\Omega(1)} error == Randomized? == Yes, Monte Carlo == Model of Computation == == Year == 2017 == Reference == https://arxiv.org/abs/1610.04712")
- 10:34, 15 February 2023 Koiliaris and Xu (Subset Sum The Subset-Sum Problem) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(min{\sqrt{n'}t, t^{5/4}, σ})$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2019 == Reference == https://dl.acm.org/doi/pdf/10.1145/3329863")
- 10:34, 15 February 2023 Psinger (Subset Sum The Subset-Sum Problem) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n max(S))$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0196677499910349")
- 10:34, 15 February 2023 Bellman dynamic programming algorithm (Subset Sum The Subset-Sum Problem) (hist | edit) [351 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n t)$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1956 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/nav.3800030107")
- 10:34, 15 February 2023 Horowitz and Sahni (Subset Sum The Subset-Sum Problem) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(n/{2})})$ == Space Complexity == $O({2}^{(n/{2})$}) (https://dl.acm.org/doi/10.1145/321812.321823) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1974 == Reference == https://dl.acm.org/doi/10.1145/321812.321823")
- 10:34, 15 February 2023 R-tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == R-Tree construction: $O(n log n)$ NNS: $O(n)$ == Space Complexity == $O(log n)$ (https://www.sciencedirect.com/science/article/pii/S1877050915019675, Table 2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference == http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf")
- 10:34, 15 February 2023 K-d Tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) (hist | edit) [373 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == k-d Tree construction: $O(n log n)$ NNS: $O(n)$ == Space Complexity == $O(n)$ (https://dl.acm.org/doi/pdf/10.1145/355744.355745) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1975 == Reference == https://dl.acm.org/doi/pdf/10.1145/355744.355745")
- 10:34, 15 February 2023 Linear search (Nearest Neighbor Search (NNS) Nearest Neighbor Search) (hist | edit) [321 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: Only ever storing the current shortest distance and the corresponding node) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference == -")
- 10:34, 15 February 2023 Zhao-Saalfeld ( Line Simplification) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (Derived: There is an auxiliary sleeve set that is $O(n)$ size worst-case) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.494.7321")
- 10:34, 15 February 2023 Lang simplification ( Line Simplification) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search line and the distance from a point in the search interval to the search line, which is all $O(1)$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == -")
- 10:34, 15 February 2023 Opheim simplification ( Line Simplification) (hist | edit) [477 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search ray and the current best, the distances from the next point to the ray and to the ray's origin, candidate point to stay in the simplified line) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1981 == Reference == http://dx.doi.org/10.2312/eg.19811012")
- 10:34, 15 February 2023 Reumann–Witkam ( Line Simplification) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search line and the distance from the next point to the line.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1974 == Reference ==")