New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:37, 15 February 2023 Thorup's algorithm (Nonnegative Integer Weights Shortest Path (Directed Graphs)) (hist | edit) [397 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E + V min(log log V, log log L))$ == Space Complexity == $O(V)$? ("linear-space queue") words (https://dl.acm.org/doi/10.1016/j.jcss.2004.04.003) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2004 == Reference == https://dl.acm.org/doi/10.1016/j.jcss.2004.04.003")
- 10:37, 15 February 2023 Gabow Ahuja Algorithm (Nonnegative Integer Weights Shortest Path (Directed Graphs)) (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E + V*((log(L))^{0.5}) )$ == Space Complexity == $O(m + log C)$ words (https://dl.acm.org/doi/10.1145/77600.77615) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://dl.acm.org/doi/10.1145/77600.77615")
- 10:37, 15 February 2023 Gabow's algorithm (Nonnegative Weights Shortest Path (Directed Graphs)) (hist | edit) [345 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E logL/log({2}+(E/V)))$ == Space Complexity == $O(V+E)$? words ((keeping track of new graphs?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1983 == Reference == https://ieeexplore.ieee.org/document/4568085")
- 10:37, 15 February 2023 Dijkstra's algorithm with Fibonacci heap (Johnson 1981; Karlsson & Poblete 1983) (Nonnegative Integer Weights Shortest Path (Directed Graphs)) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E log log L)$ == Space Complexity == $O(V+L)$ words (https://www.sciencedirect.com/science/article/pii/0166218X8390104X?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://www.sciencedirect.com/science/article/pii/0166218X8390104X?via%3Dihub")
- 10:37, 15 February 2023 Dijkstra's algorithm with Fibonacci heap (Fredman & Tarjan 1984; Fredman & Tarjan 1987) (Nonnegative Weights Shortest Path (Directed Graphs)) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E + V log V)$ == Space Complexity == $O(V)$ auxiliary words (keeping track of distances/previous node in path, along with heap) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1984 == Reference == https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/fibonacci%20heaps.pdf")
- 10:37, 15 February 2023 Dijkstra's algorithm with binary heap (Johnson 1977) (Nonnegative Weights Shortest Path (Directed Graphs)) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((E + V) log V)$ == Space Complexity == $O(V)$ auxiliary words (keeping track of distances/previous node in path, along with heap) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=321993")
- 10:37, 15 February 2023 Dijkstra's algorithm with list (Whiting & Hillier 1960) (Nonnegative Weights Shortest Path (Directed Graphs)) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( V² )$ == Space Complexity == $O(V)$ auxiliary words (keeping track of distances/previous node in path, along with list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1960 == Reference == https://www.jstor.org/stable/3007178?seq=1#page_scan_tab_contents")
- 10:37, 15 February 2023 Bellman–Ford algorithm (Dantzig 1960) (Nonnegative Weights Shortest Path (Directed Graphs)) (hist | edit) [329 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( V² logV)$ == Space Complexity == $O(E)$ (total) words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1960 == Reference == https://www.jstor.org/stable/pdf/2627005.pdf")
- 10:37, 15 February 2023 Bellman–Ford algorithm (Shimbel 1955; Bellman 1958; Moore 1959) (general weights Shortest Path (Directed Graphs)) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(V)$ auxiliary words (keeping track of distances) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1959 == Reference == https://www.ams.org/journals/qam/1958-16-01/S0033-569X-1958-0102435-2/S0033-569X-1958-0102435-2.pdf")
- 10:37, 15 February 2023 Bellman–Ford algorithm (Ford 1956) (general weights Shortest Path (Directed Graphs)) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( V² EL)$ == Space Complexity == $O(E)$ words (number of equations in LP; each equation has a constant number of variables) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1956 == Reference == https://apps.dtic.mil/sti/pdfs/AD0422842.pdf")
- 10:37, 15 February 2023 Dyer (2-dimensional array representation Closest Pair Problem) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ using $O(n^{2})$ processors == Space Complexity == $O(n^{2})$ words (https://www.sciencedirect.com/science/article/pii/0020019080900356) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == log-space pyramid cellular automaton == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0020019080900356")
- 10:37, 15 February 2023 Shamos; Hoey (2-dimensional space, Euclidean metric Closest Pair Problem) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words (Voronoi diagrams require O(n) space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1975 == Reference == https://ieeexplore.ieee.org/document/4567872")
- 10:37, 15 February 2023 Hinrichs; Nievergelt; Schorn (2-dimensional space, l m (or l infty) norm Closest Pair Problem) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0020019088901500) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1988 == Reference == https://www.sciencedirect.com/science/article/pii/0020019088901500")
- 10:37, 15 February 2023 Bentley; Shamos (k-dimensional space, l m (or l infty) norm Closest Pair Problem) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn logn)$ == Space Complexity == $O(kn)$? words (keep track of all sorted lists in each dimension; re-use space from recursive calls) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1976 == Reference == https://dl.acm.org/citation.cfm?id=803652")
- 10:37, 15 February 2023 Bentley (k-dimensional space, l m (or l infty) norm Closest Pair Problem) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn logn)$ == Space Complexity == $O(kn)$? words (keep track of all sorted lists in each dimension; re-use space from recursive calls) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1980 == Reference == https://dl.acm.org/citation.cfm?id=358850")
- 10:37, 15 February 2023 Rabin' Algorithm (k-dimensional space, l m (or l infty) norm Closest Pair Problem) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^k*n^{2})$ == Space Complexity == $O(n)$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Real RAM == Year == 1976 == Reference == https://dl.acm.org/citation.cfm?id=540196")
- 10:37, 15 February 2023 F. Preparata and M. Shamos (k-dimensional space, l m (or l infty) norm Closest Pair Problem) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn logn)$ == Space Complexity == $O(kn)$? words (keep track of all sorted lists in each dimension; re-use space from recursive calls) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://www.springer.com/gp/book/9780387961316")
- 10:37, 15 February 2023 Fortune and Hopcroft (k-dimensional space, l m (or l infty) norm Closest Pair Problem) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn loglogn+n*{3}^k)$ == Space Complexity == $O(n)$ words (can be easily derived? (can re-use space from recursive calls)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1979 == Reference == https://www.sciencedirect.com/science/article/pii/0020019079900851")
- 10:37, 15 February 2023 Thorup (reverse-delete) (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E LogV (loglogV)^{3})$ == Space Complexity == $O(E)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf")
- 10:37, 15 February 2023 Chazelle's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [504 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E*\alpha(E, V))$ == Space Complexity == $O(E)$ auxiliary?? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.cs.princeton.edu/~chazelle/pubs/mst.pdf")
- 10:37, 15 February 2023 Filter Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(Elog(V))$ == Space Complexity == $O(E)$ auxiliary? words (Kruskal-based, with minimal overhead? filtering should only remove edges, and each edge should only require O(1) information) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == https://dl.acm.org/citation.cfm?id=2791225")
- 10:37, 15 February 2023 Cheriton-Tarjan Algorithm (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(EloglogV)$ == Space Complexity == $O(E)$ auxiliary? words (keep track of copy of graph where edges may be deleted?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://epubs.siam.org/doi/abs/10.1137/0205051")
- 10:37, 15 February 2023 Yao's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(EloglogV)$ == Space Complexity == $O(E)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.sciencedirect.com/science/article/pii/0020019075900563")
- 10:37, 15 February 2023 Kruskal's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(ElogE)$ == Space Complexity == $O(E)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://www.jstor.org/stable/2033241")
- 10:37, 15 February 2023 Prim's algorithm + Fibonacci heaps; Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E + VlogV)$ == Space Complexity == $O(V)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://dl.acm.org/citation.cfm?id=28874")
- 10:37, 15 February 2023 Prim's algorithm + adjacency matrix searching (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1957 == Reference == https://ieeexplore.ieee.org/document/6773228")
- 10:37, 15 February 2023 Borůvka's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [279 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(ElogV)$ == Space Complexity == $O(V)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1926 == Reference == -")
- 10:37, 15 February 2023 Hong’s algorithm (SCCs Strongly Connected Components) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V(V+E))$ == Space Complexity == $O(V+E)$? words (Building recursive subgraphs) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://stanford-ppl.github.io/website/papers/sc13-hong.pdf")
- 10:37, 15 February 2023 CH Algorithm (SCCs Strongly Connected Components) (hist | edit) [423 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(V+E)$? words (Each vertex needs to keep track of one color; then we need to build recursive subgraphs) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://research.vu.nl/en/publications/on-distributed-verification-and-verified-distribution")
- 10:37, 15 February 2023 OBF Algorithm (SCCs Strongly Connected Components) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V(V+E))$ == Space Complexity == $O(E+V^{2})$ total words (https://ris.utwente.nl/ws/files/6872352/Barnat09distributed.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://ieeexplore.ieee.org/document/8133154")
- 10:37, 15 February 2023 Munro’s algorithm (SCCs Strongly Connected Components) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E + VlogV)$ == Space Complexity == $O(V)$? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://www.sciencedirect.com/science/article/pii/0020019071900068")
- 10:37, 15 February 2023 Couvreur (SCCs Strongly Connected Components) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/chapter/10.1007/3-540-48119-2_16")
- 10:37, 15 February 2023 Renault’s Algorithm (SCCs Strongly Connected Components) (hist | edit) [359 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(p*(V+E)*\alpha(V, E))$ == Space Complexity == $O(V)$ per processor words ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == https://link.springer.com/chapter/10.1007/978-3-642-45221-5_44")
- 10:37, 15 February 2023 Lowe’s Algorithm (SCCs Strongly Connected Components) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V)$ per processor words ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == http://www.cs.ox.ac.uk/people/gavin.lowe/parallelDFS.html")
- 10:37, 15 February 2023 Paul Purdom (Transitive Closure Strongly Connected Components) (hist | edit) [365 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}+VE)$ == Space Complexity == $O(V^{2})$ words (https://link.springer.com/content/pdf/10.1007/BF01940892.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://link.springer.com/article/10.1007%2FBF01940892")
- 10:37, 15 February 2023 Path-based depth-first search Gabow (SCCs Strongly Connected Components) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V+E)$ total, $O(V)$ auxiliary? words (https://www.sciencedirect.com/science/article/pii/S002001900000051X?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.sciencedirect.com/science/article/pii/S002001900000051X?via%3Dihub")
- 10:37, 15 February 2023 Pearce (SCCs Strongly Connected Components) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ words (https://www.sciencedirect.com/science/article/pii/S0020019015001532) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://www.sciencedirect.com/science/article/pii/S0020019015001532")
- 10:37, 15 February 2023 Fleischer forward-backward (FB) algorithm (SCCs Strongly Connected Components) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(ElogV+V)$ == Space Complexity == $O(V+E)$ words (constructing recursive subgraphs? and reuse space across recursive calls) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://ldhulipala.github.io/readings/sequential-scc.pdf")
- 10:37, 15 February 2023 Path-based strong components algorithm; Dijkstra (SCCs Strongly Connected Components) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ words (constant number of auxiliary stacks?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://www.worldcat.org/title/discipline-of-programming/oclc/1958445")
- 10:37, 15 February 2023 Tarjan's strongly connected components algorithm (SCCs Strongly Connected Components) (hist | edit) [441 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ words (https://www.sciencedirect.com/science/article/pii/S0020019015001532) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://www.semanticscholar.org/paper/Depth-First-Search-and-Linear-Graph-Algorithms-Tarjan/385742fffcf113656f0d3cf6c06ef95cb8439dc6")
- 10:36, 15 February 2023 Kosaraju's algorithm (SCCs Strongly Connected Components) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V+E)$ words (auxiliary data structures take up at most that much space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://www.sciencedirect.com/science/article/pii/0898122181900080")
- 10:36, 15 February 2023 Miller; Stout (2-dimensional Convex Hull) (hist | edit) [463 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ time using $O(n)$ processors == Space Complexity == $O(n)$ total? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM, possibly others (see paper) == Year == 1988 == Reference == https://cse.buffalo.edu/faculty/miller/Papers/IEEETC88a.pdf")
- 10:36, 15 February 2023 Chan's algorithm (2-dimensional; 3-dimensional Convex Hull) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log h)$ == Space Complexity == $O(n)$ words (https://link.springer.com/article/10.1007/BF02712873) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1996 == Reference == https://link.springer.com/article/10.1007/BF02712873")
- 10:36, 15 February 2023 The ultimate planar convex hull algorithm (2-dimensional Convex Hull) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log h)$ == Space Complexity == $O(n)$ words (https://ecommons.cornell.edu/handle/1813/6417) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://ecommons.cornell.edu/handle/1813/6417")
- 10:36, 15 February 2023 Andrew's algorithm (2-dimensional Convex Hull) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1979 == Reference == https://www.sciencedirect.com/science/article/pii/0020019079900723")
- 10:36, 15 February 2023 Preparata and Hong (2-dimensional; 3-dimensional Convex Hull) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$?? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=359430")
- 10:36, 15 February 2023 W. Eddy Quickhull (2-dimensional Convex Hull) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nh)$ == Space Complexity == $O(h)$? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=355766")
- 10:36, 15 February 2023 Graham (2-dimensional Convex Hull) (hist | edit) [345 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1972 == Reference == https://www.sciencedirect.com/science/article/pii/0020019072900452?via%3Dihub")
- 10:36, 15 February 2023 Goodrich (Reporting all intersection points, line segments Line segment intersection) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{2}(n))$ == Space Complexity == $O(n+k)$ total? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1989 == Reference == https://dl.acm.org/citation.cfm?id=72950")
- 10:36, 15 February 2023 Boissonnat; Snoeyink (Reporting all intersection points, generalized segments Line segment intersection) (hist | edit) [398 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( nlog n + k )$ == Space Complexity == $O(n)$ words (https://dl.acm.org/citation.cfm?id=304991) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM, under more restrictions/considerations? (predicate arithmetic) == Year == 1999 == Reference == https://dl.acm.org/citation.cfm?id=304991")