New pages

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

• 11:15, 15 February 2023 ‎Kong and Wilken Algorithm (Global Register Allocation Register Allocation) (hist | edit) ‎[368 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == ? Probably also dependent on the ILP solver () == Description == Integer programming for irregular register architectures == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://dl.acm.org/doi/10.5555/290940.291002")
• 11:15, 15 February 2023 ‎Optimal Register Allocation (ORA), Goodwin & Wilken Algorithm (Global Register Allocation Register Allocation) (hist | edit) ‎[478 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == Depends on the choice of {0}-{1} ILP solver ("Memory usage is dominated by the usage of the integer program solver.") == Description == 0-1 integer linear programming problem == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-024X%28199608%2926%3A8%3C929%3A%3AA...")
• 11:15, 15 February 2023 ‎Cooper and Dasgupta algorithm ( Register Allocation) (hist | edit) ‎[222 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference ==")
• 11:15, 15 February 2023 ‎Linear Scan, Poletto & Sarkar (Global Register Allocation Register Allocation) (hist | edit) ‎[471 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(r)$ words (Derived: given the live ranges, the only auxiliary data structure is an "active" list that contains the active live ranges and this has length at most $r$) == Description == Greedy assignment == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf")
• 11:15, 15 February 2023 ‎Chow's Algorithm (Global Register Allocation Register Allocation) (hist | edit) ‎[479 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm also uses a register interference graph (RIG)) == Description == Assumes all variables allocated in main memory (i.e. assumes no spill handling required). Priority-based RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/502874.50...")
• 11:15, 15 February 2023 ‎Chaitin's Algorithm (Global Register Allocation Register Allocation) (hist | edit) ‎[432 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm uses both an adjacency matrix (called the bit matrix) and adjacency lists (called the adjacency vectors)) == Description == RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://dl.acm.org/doi/10.1145/872726.806984")
• 11:15, 15 February 2023 ‎Bottom-m sketches streaming algorithm (streaming Cardinality Estimation) (hist | edit) ‎[339 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(m)$ words (only keep track of m minimum values. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
• 11:15, 15 February 2023 ‎Min/max sketches streaming algorithm (streaming Cardinality Estimation) (hist | edit) ‎[338 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O({1})$ words (only keep track of minimum value. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
• 11:15, 15 February 2023 ‎HyperLogLog algorithm ( Cardinality Estimation) (hist | edit) ‎[417 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words (https://oertl.github.io/hyperloglog-sketch-estimation-paper/paper/paper.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2007 == Reference == http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf")
• 11:15, 15 February 2023 ‎HyperLogLog++ ( Cardinality Estimation) (hist | edit) ‎[392 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words ((see hyperloglog?)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2014 == Reference == https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf")
• 11:15, 15 February 2023 ‎LogLog algorithm ( Cardinality Estimation) (hist | edit) ‎[384 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log(log(n)$)) words (http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2003 == Reference == http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf")
• 11:15, 15 February 2023 ‎Flajolet–Martin algorithm ( Cardinality Estimation) (hist | edit) ‎[386 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log n)$ words (https://www.sciencedirect.com/science/article/pii/S0022000097915452) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1984 == Reference == http://algo.inria.fr/flajolet/Publications/src/FlMa85.pdf")
• 11:15, 15 February 2023 ‎Naive solution ( Cardinality Estimation) (hist | edit) ‎[302 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(n)$ words (keep track of exact histogram, may require storing all values) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 ‎Generalized expectation maximization (GEM) algorithm ( Maximum Likelihood Parameters) (hist | edit) ‎[485 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4} log^{0.{1}.5}n)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1994 == Reference == https://web.eecs.umich.edu/~fessler/papers/files/jour/94/web/fessler-94-...")
• 11:15, 15 February 2023 ‎Α-EM algorithm ( Maximum Likelihood Parameters) (hist | edit) ‎[440 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of alpha-log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1109/TIT.2002.808105")
• 11:15, 15 February 2023 ‎Expectation conditional maximization (ECM) ( Maximum Likelihood Parameters) (hist | edit) ‎[427 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://arxiv.org/abs/1709.06970")
• 11:15, 15 February 2023 ‎Parameter-expanded expectation maximization (PX-EM) algorithm ( Maximum Likelihood Parameters) (hist | edit) ‎[434 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta (+ alpha) and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1998 == Reference == https://www.jstor.org/stable/2337481")
• 11:15, 15 February 2023 ‎Newton–Raphson algorithm ( Maximum Likelihood Parameters) (hist | edit) ‎[450 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r^{2})$? words (Stores current theta guess, which is updated each iteration, and requires computation of the (inverse of the) Hessian matrix. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1685 == Reference == -")
• 11:15, 15 February 2023 ‎Knuth–Bendix algorithm (General Groups (uncompleted?) Coset Enumeration) (hist | edit) ‎[462 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.5}^n n^{2} logn)$ == Space Complexity == $O(ng)$??? words (Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1970 == Reference == https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf")
• 11:15, 15 February 2023 ‎Expectation–maximization (EM) algorithm ( Maximum Likelihood Parameters) (hist | edit) ‎[424 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://www.jstor.org/stable/2984875")
• 11:15, 15 February 2023 ‎Todd–Coxeter algorithm (Bounded Subgroup Index Coset Enumeration) (hist | edit) ‎[501 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(gkc)$ words (Defines O(k) tables, each with O(g) columns and O(c) rows) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1936 == Reference == https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/practical-method-for-enumerating-cosets-of-a-finite-abstract-group/030657...")
• 11:15, 15 February 2023 ‎Haselgrove; Leech and Trotter (Bounded Subgroup Index Coset Enumeration) (hist | edit) ‎[387 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(ng)$? words (Implementation stores a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
• 11:15, 15 February 2023 ‎Muller's method (General Root Computation Root Computation) (hist | edit) ‎[479 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1956 == Reference == https://www.jstor.org/stable/200...")
• 11:15, 15 February 2023 ‎Ridder's method (General Root Computation Root Computation) (hist | edit) ‎[478 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference == https://ieeexplore.ieee.org/document/1084580/")
• 11:15, 15 February 2023 ‎Secant method (General Root Computation Root Computation) (hist | edit) ‎[434 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 ‎Newton's method (Root Computation with continuous first derivative Root Computation) (hist | edit) ‎[479 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate $x_i$ and the derivative $f'$ (assuming this takes $O(1)$ space); iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Referenc...")
• 11:15, 15 February 2023 ‎Halley's method (Root Computation with continuous second derivative Root Computation) (hist | edit) ‎[482 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate x_i and the derivatives f' and f'' (assuming this takes O(1) space); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference...")
• 11:15, 15 February 2023 ‎False position method (General Root Computation Root Computation) (hist | edit) ‎[425 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1690 == Reference == -")
• 11:15, 15 February 2023 ‎Bisection method (General Root Computation Root Computation) (hist | edit) ‎[425 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1820 == Reference == -")
• 11:15, 15 February 2023 ‎MRRR algorithm (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[426 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words (Need to compute and store some matrix of the form $(A-mu*I)^{(-1)}$ (for inverse iteration-like uses)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1999 == Reference == https://www.cs.utexas.edu/users/inderjit/public_papers/DesignMRRR_toms06.pdf")
• 11:15, 15 February 2023 ‎Homotopy method (All eigenpairs; Eigenpair closest to mu; Any eigenpair; Any eigenvalue; All eigenvalues Eigenvalues (Iterative Methods)) (hist | edit) ‎[403 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$?? words (Conservative bound on space used per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://www.scirp.org/(S(czeh2tfqyw2orz553k1w0r45))/reference/ReferencesPapers.aspx?ReferenceID=530065")
• 11:15, 15 February 2023 ‎Folded spectrum method (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[438 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of O(n)-sized vectors per iteration; matrix-to-vector multiplication only requires O(n) aux space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1934 == Reference == https://journals.aps.org/pr/abstract/10.1103/PhysRev.46.828")
• 11:15, 15 February 2023 ‎Divide-and-conquer (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[411 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n^{2})$ words (Stores reduction to tridiagonal form; recursion (S(n)=2S(n/2)+O(n^2)) should work out to O(n^2)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == https://link.springer.com/content/pdf/10.1007/BF01389480.pdf")
• 11:15, 15 February 2023 ‎Jacobi eigenvalue algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[355 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computes and stores results of GSG^T iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1846 == Reference == https://gdz.sub.uni-goettingen.de/id/PPN243919689_0030")
• 11:15, 15 February 2023 ‎QR algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[361 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores QR factorization at each iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1962 == Reference == https://academic.oup.com/comjnl/article/4/4/332/432033")
• 11:15, 15 February 2023 ‎Laguerre iteration (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[266 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (^ see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 ‎Bisection method (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[424 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computing characteristic polynomial takes $O(n^2)$ space (via e.g. Faddeev–LeVerrier algorithm); rest of algo can be done in $O(n)$ space (related to root computation)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1985 == Reference == -")
• 11:15, 15 February 2023 ‎LOBPCG algorithm (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[320 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of $O(n)$-sized vectors per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1948 == Reference == -")
• 11:15, 15 February 2023 ‎Rayleigh quotient iteration (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[299 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu_i*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 ‎Inverse iteration (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[360 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1921 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/zamm.19210010104")
• 11:15, 15 February 2023 ‎Weiler–Atherton clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) ‎[382 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf")
• 11:15, 15 February 2023 ‎Vatti clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/129902.129906")
• 11:15, 15 February 2023 ‎Sutherland–Hodgman algorithm (Polygon Clipping with Convex Clipping Polygon Polygon Clipping) (hist | edit) ‎[464 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ auxiliary words (Each iteration, keeps track of updated polygon after clipping by a side. Note that there can be at most $O(n)$ intersection points due to the clipping polygon being convex) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1974 == Reference == https://dl.acm.org/doi/10.1145/360767.360802")
• 11:15, 15 February 2023 ‎Gupta-Sproull algorithm (Line Drawing Line Drawing) (hist | edit) ‎[459 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1981 == Reference == http://www.cs.gettysburg.edu/~ilinkin/courses/Fall-2014/cs373/handouts/papers/gs-fegsd-81.pdf")
• 11:15, 15 February 2023 ‎Greiner–Hormann clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1998 == Reference == http://davis.wpi.edu/~matt/courses/clipping/")
• 11:15, 15 February 2023 ‎Bresenham's line algorithm (Line Drawing Line Drawing) (hist | edit) ‎[442 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1965 == Reference == https://web.archive.org/web/20080528040104/http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf")
• 11:15, 15 February 2023 ‎Xiaolin Wu's line algorithm (Line Drawing Line Drawing) (hist | edit) ‎[423 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1991 == Reference == http://www-users.mat.umk.pl/~gruby/teaching/lgim/1_wu.pdf")
• 11:15, 15 February 2023 ‎Digital Differential Analyzer (Line Drawing Line Drawing) (hist | edit) ‎[343 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 ‎Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[378 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn loglogn)$ == Space Complexity == $O(n)$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2010 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613")
• 11:15, 15 February 2023 ‎Naive algorithm (Line Drawing Line Drawing) (hist | edit) ‎[343 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")

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