All public logs

Combined display of all available logs of Algorithm Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 10:52, 15 February 2023 Admin talk contribs created page Fortune (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (See incremental/flipping algorithm space complexities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/142675.142695")
• 10:52, 15 February 2023 Admin talk contribs created page Dwyer (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Space recursion is S(n)=max(2S(n/2), O(n)) as triangulations from recursive calls are modified in the merge step) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840356")
• 10:52, 15 February 2023 Admin talk contribs created page S-hull (Sinclair) (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2010 == Reference == http://www.s-hull.org/paper/s_hull.pdf")
• 10:52, 15 February 2023 Admin talk contribs created page Guibas; Stofli (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Space recursion is S(n)=max(2S(n/2), O(n)) as triangulations from recursive calls are modified in the merge step) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1985 == Reference == http://www.geom.uiuc.edu/~samuelp/del_project.html")
• 10:52, 15 February 2023 Admin talk contribs created page Bowyer–Watson algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1981 == Reference == https://academic.oup.com/comjnl/article/24/2/167/338200")
• 10:52, 15 February 2023 Admin talk contribs created page Belloch (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove (see other incremental algos)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2006 == Reference == https://web.archive.org/web/20180425231851/https://www.cs.cmu.edu/~ygu1/pape...")
• 10:52, 15 February 2023 Admin talk contribs created page De Berg; Cheong (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2008 == Reference == https://web.archive.org/web/20091028054315/http://www.cs.uu.nl/geobook/interpolation.pdf")
• 10:52, 15 February 2023 Admin talk contribs created page Naive algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (Created page with "== Time Complexity == $O(n^{4})$? (previously $O(n^{2})$) == Space Complexity == $O(n)$ words (Keep track of triangles in triangulation, and current triangle being tested) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1934 == Reference == -")
• 10:52, 15 February 2023 Admin talk contribs created page Flipping algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keep track of edges in current triangulation) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1999 == Reference == https://link.springer.com/article/10.1007/PL00009464")
• 10:52, 15 February 2023 Admin talk contribs created page 9-point FFT (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1978 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 5-point cyclic reduction (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1970 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 9-point ADI iteration + smooth guess (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1969 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 5-point FFT (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 9-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 9-point Tensor product (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1964 == Reference == https://epubs.siam.org/doi/pdf/10.1137/0113067")
• 10:52, 15 February 2023 Admin talk contribs created page 5-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{4} logn)$ == Space Complexity == $O(n^{3})$? words (Need one auxiliary O(n^3)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1954 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 9-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$? words (Need one auxiliary O(n^3)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1956 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 5-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{3} log^{2}n)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1955 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 5-point Gauss Seidel iteration (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{5} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 5-point Gauss elimination (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{7})$ == Space Complexity == $O(n^{6})$ words (See Gauss-Jordan elimination, but matrix is of size n^3*n^3) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
• 10:52, 15 February 2023 Admin talk contribs created page 5-point star Cramer's rule (3-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O({5}^{(n^{3})$}) == Space Complexity == $O({5}^{(n^{3})})$ for sure, $O(n^{3})$ possibly??? (if super conservative) words (For expansion by minors, each "level" of expansion requires computing and storing O(1) smaller determinants, and there are O(n^3) levels overall) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page Chin and Poon (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O(sn + \min\{sp, rm\})$ == Space Complexity == $O(p + n)$ words (https://link.springer.com/content/pdf/10.1007/3-540-58338-6_63.pdf, Fig. 3) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://dl.acm.org/citation.cfm?id=105592")
• 10:42, 15 February 2023 Admin talk contribs created page Apostolico and Guerra (Algorithm 2) (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O(rm + sn + n \log s)$ == Space Complexity == $O(p + sn)$ words (https://link.springer.com/content/pdf/10.1007/BF01840365.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840365")
• 10:42, 15 February 2023 Admin talk contribs created page Hsu and Du (Scheme 1) (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O(rm \log(n/m)$ + rm) == Space Complexity == $O(rm)$ words (https://www.sciencedirect.com/science/article/pii/0022000084900254) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/0022000084900254")
• 10:42, 15 February 2023 Admin talk contribs created page Hirschberg (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O(rn + n \log n)$ == Space Complexity == $O(n + p)$ words (https://link.springer.com/content/pdf/10.1007/BF01840365.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=322044")
• 10:42, 15 February 2023 Admin talk contribs created page Rick (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O(sn + \min\{r(n - r )$, rm\}) == Space Complexity == $O(sn + p)$ words (https://link.springer.com/chapter/10.1007%2F3-540-60044-2_53) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://link.springer.com/chapter/10.1007%2F3-540-60044-2_53")
• 10:42, 15 February 2023 Admin talk contribs created page Kuo and Cross (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O(p + n(r+\log n)$) == Space Complexity == $O(p + n)$ words (https://dl.acm.org/doi/10.1145/74697.74702, Same space complexity as Hunt and Szymanski.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://dl.acm.org/citation.cfm?id=74702")
• 10:42, 15 February 2023 Admin talk contribs created page Apostolico and Guerra (HS1 Algorithm) (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O(m \log n +p \log({2}mn/p)$) == Space Complexity == $O(p + n)$ words (https://link.springer.com/article/10.1007/BF01840365) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840365")
• 10:42, 15 February 2023 Admin talk contribs created page Hsu and Du (Scheme 2) (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O(rm \log(n/r)$ + rm) == Space Complexity == $O(rm)$ words (https://www.sciencedirect.com/science/article/pii/0022000084900254) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/0022000084900254")
• 10:42, 15 February 2023 Admin talk contribs created page Czumaj (Matrix Chain Scheduling Problem Matrix Chain Multiplication) (Created page with "== Time Complexity == $O(log^{3} n)$ == Space Complexity == $O(n^{2})$? words (Derived: uses two arrays ($D$ and $c$) both of size $O(n^2)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1993 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.9426&rep=rep1&type=pdf")
• 10:42, 15 February 2023 Admin talk contribs created page Prakesh Ramanan (Approximate MCOP Matrix Chain Multiplication) (Created page with "== Time Complexity == $O(log^{4} n)$ == Space Complexity == $O(n)$? words (Derived: $n$ subtrees and each one has a $O(1)$ size trunk) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1996 == Reference == https://epubs.siam.org/doi/abs/10.1137/0225039")
• 10:42, 15 February 2023 Admin talk contribs created page Heejo Lee; Jong Kim; Sungje Hong; and Sunggu Lee (Approximate MCSP Matrix Chain Multiplication) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Derived: two $n \times n$ size tables ($S$ and $W$)) == Description == == Approximate? == Approximate Approximation Factor: "near optimal" == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.222&rep=rep1&type=pdf")
• 10:42, 15 February 2023 Admin talk contribs created page Spaghetti Sort Parallel Implementation (Non-Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? per processor? words (Assuming getting the spaghetti rods doesn't take up any auxiliary space, the only auxiliary space in this algorithm involves the table and the hands, each using O(1) space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == ??? == Year == 1984 == Reference == https://link.springer.com/chapter/10.1007...")
• 10:42, 15 February 2023 Admin talk contribs created page Odd Even Sort Parallel Implementation (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (in-situ) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://www.semanticscholar.org/paper/Parallel-Neighbor-Sort-(or-the-Glory-of-the-Habermann/bc7b6efb99aae6225239425747fd0169a51f30ce")
• 10:42, 15 February 2023 Admin talk contribs created page Probabilistic Convolution Tree (Change-Making Problem Change-Making Problem) (Created page with "== Time Complexity == $O(n log n)$ == Space Complexity == $O(n log n)$ words (https://pubmed.ncbi.nlm.nih.gov/24626234/) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/24626234")
• 10:42, 15 February 2023 Admin talk contribs created page Srba (SLAM Algorithms SLAM Algorithms) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words? (Seems to store a constant number of O(n)*O(n)-sized matrices and O(n)*O(n)-sized tables (see section II, part C)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == http://ingmec.ual.es/~jlblanco/papers/blanco2013rba.pdf")
• 10:42, 15 February 2023 Admin talk contribs created page FastSlam (SLAM Algorithms SLAM Algorithms) (Created page with "== Time Complexity == $O(m*log n)$ per iteration == Space Complexity == $O(mn)$? words? (Stores and updates a balanced binary tree of n elements/dimensions per particle) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == http://robots.stanford.edu/papers/montemerlo.fastslam-tr.pdf")
• 10:42, 15 February 2023 Admin talk contribs created page Maximum a Posteriori Occupancy Mapping (Occupancy Grid Mapping Occupancy Grid Mapping) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page HEALPix mapping Wong (Environment Mapping Texture Mapping) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page Mauro Steigleder (Environment Mapping Texture Mapping) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page Emil Praun (Environment Mapping Texture Mapping) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page Heidrich; W.; and H.-P. Seidel (Environment Mapping Texture Mapping) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page Sphere mapping (Environment Mapping Texture Mapping) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page Nate Green (Environment Mapping Texture Mapping) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1986 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page Blinn and Newell (Environment Mapping Texture Mapping) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1976 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page Bresenham Algorithm (Rasterization Rasterization) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ Words (Derived: for each iteration (i.e. each step along the line), only need to store a constant number of variables that are then overwritten in the next iteration.) == Description == == Approximate? == Approximate Approximation Factor: n/a == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == Hearn, Baker (1997) pg. 88")
• 10:42, 15 February 2023 Admin talk contribs created page Digital Differential Analyzer (DDA) (Rasterization Rasterization) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ Words (Derived: for each iteration (i.e. each step along the line), only need to store a constant number of variables that are then overwritten in the next iteration.) == Description == "Scan-conversion line algorithm" == Approximate? == Approximate Approximation Factor: n/a == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == Hearn, Ba...")
• 10:42, 15 February 2023 Admin talk contribs created page Shani; Brafman; & Shimony; 2005 (POMDPs POMDPs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page Bertsekas & Castanon; 1999; (POMDPs POMDPs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference ==")
• 10:42, 15 February 2023 Admin talk contribs created page McAllester & Singh; 1999; (POMDPs POMDPs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference ==")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)