<p>Chazelle gave a linear time algorithm for <a href="http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf">triangulating a simple polygon</a>. Skiena wrote (p.575, Algorithm Design Manual) that it's "sufficiently hopeless to implement that it qualifies more as an existence proof"</p>

CC BY-SA 3.0
2013-11-17T22:17:39.067Z
Is this the only known linear time algorithm for the problem?
Thomas Ahle
CC BY-SA 3.0
2014-02-20T21:41:08.077Z
@ThomasAhle I believe it is the only known deterministic linear time algorithm. Amato, Goodrich, and Ramos have a simpler randomized one: https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/linear%20time%20triangulation.pdf
Sasho Nikolov
CC BY-SA 3.0
2015-10-11T02:01:21.790Z
Chazelle's linear time simple polygon triangulation algorithm, to my knowledge, has never been implemented and likely never will be because
of it's complexity and also because constants are high so it won't be
able to compete with alternatives in practice. Major theoretical achievement though. Ralph Boland
Ralph Boland
CC BY-SA 3.0
2017-05-02T20:03:31.100Z
I'll ask again: Does the algorithm have reasonable constants?
user1271772
CC BY-SA 4.0
2018-07-24T22:11:14.583Z
@user1271772: I don't believe anybody has made a serious effort to figure out whether there's a version of Chazelle's algorithm with reasonable constants. Since there are several very simple $O(n\log n)$ algorithms with small constants, the amount of computation time it would save is clearly dwarfed by the enormous cost of programming it up. You probably never want to triangulate any polygons with more than a few hundred edges, and for this size it's hard to imagine it could beat the $O(n \log n)$ algorithms.
Peter Shor 
CC BY-SA 2.5
2011-01-25T08:01:05.343Z
Does the algorithm have reasonable constants?
jbapple
CC BY-SA 2.5
2011-01-23T03:05:48.600Z
2011-01-24T02:52:06.660Z
2011-01-24T02:52:06.660Z
Yaroslav Bulatov
<p>The <a href="http://en.wikipedia.org/wiki/Risch_algorithm">Risch algorithm</a> for computing elementary antiderivatives. According to Wikipedia, no software package is known to implement the full algorithm due to its complexity.</p>

CC BY-SA 2.5
2011-01-25T15:22:59.643Z
Wikipedia also points out that this is not an algorithm but a semi-algorithm because it requires heuristics for solving the constant problem.
sclv
CC BY-SA 3.0
2016-01-05T17:31:17.843Z
What is heuristics? Can you give some link to read more about it?
zygimantus
CC BY-SA 2.5
2011-01-23T08:25:02.013Z
2011-01-23T08:25:02.013Z
Mark Reitblatt
<p>Dan Willard's <a href="http://scholar.google.com/scholar?cluster=9370873690129514324">"A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time"</a> describes an algorithm for maintaining an ordered set in an array of size $O(n)$ with insertion and deletion in $O(\frac{\log^2 n}{B})$ worst-case time, where $B$ is the page size.</p>

<p>The paper is 55 pages long, and its conclusion notes several improvements to the constants that the author does not describe for reasons of space. This makes me suspect that perhaps the constants aren't so galactic, and that this data structure would be of "legitimate utility", especially since it has been cited many times.</p>

CC BY-SA 2.5
2011-01-23T20:47:06.660Z
2011-01-23T21:10:56.100Z
2011-01-23T21:10:56.100Z
jbapple
<p>Any algorithm that uses the Robertson-Seymour results to infer a "polytime" algorithm for things involving graphs that exclude a fixed minor is asking for trouble. The constant hidden in their result is "galactic". </p>

CC BY-SA 2.5
2011-01-23T23:52:42.507Z
Is this also hard to implement or just has a huge constant?
Lev Reyzin
CC BY-SA 2.5
2011-01-24T00:43:17.973Z
Yes, this does not look like a good example. If I understand correctly, the question is about algorithms which could be practical (hence likely 'small' constants) but are just too complex to implement. Of course, the whole question is open to different interpretations :-)
Aryabhata
CC BY-SA 2.5
2011-01-24T05:08:03.563Z
The problem is the constant comes from the very large list of minors that one needs to exclude for a particular property. I don't know of any way to generate the desired list of excluded minors for a given property, so it's not just a scale issue .
Suresh Venkat
CC BY-SA 2.5
2011-01-24T15:00:46.713Z
For instance, we don't even know the list of excluded minors for graphs embeddable in the torus.
Derrick Stolee
CC BY-SA 2.5
2011-01-24T17:42:31.267Z
Interesting.  Perhaps this should be added to the answer...
Lev Reyzin
CC BY-SA 2.5
2011-01-24T18:21:51.430Z
The problem here seems deeper: there is no _effective_ way known to generate the list of minors, so this doesn't actually yield an algorithm at all.  Most minor-closed properties yield an infinite list of excluded minors, if one translates the logical expression directly.  The Robertson-Seymour Theorem (Wagner's Conjecture) tells us that a finite list of excluded minors is lurking inside that infinite list, but the theorem gives absolutely no help in actually finding them.   So Robertson-Seymour therefore usually leads to a pure existence proof.
András Salamon
CC BY-SA 2.5
2011-01-25T00:40:51.650Z
isn't it therefore "too complex to implement" ? :)
Suresh Venkat
CC BY-SA 2.5
2011-01-26T01:11:17.100Z
@Suresh: I don't think the complexity is in question here. Whether the algorithm satisfies the question constraint of "could have practical value" is in doubt :-)
Aryabhata
CC BY-SA 3.0
2011-11-30T23:44:32.837Z
Isn't even compiling a single graph $H$ into the $O(n^3)$ algorithm to test for having $H$ as a minor an extremely difficult task?  Hasn't the full algorithm only been implemented once or something?
Jeff Burdges
CC BY-SA 3.0
2017-05-02T20:10:06.483Z
-1 because the constant is "galactic" and the question went through exceptional effort to request NOT giving such an algorithm.
user1271772
CC BY-SA 2.5
2011-01-23T09:26:26.033Z
2011-01-23T09:26:26.033Z
Suresh Venkat
<p>The linear time higher-order pattern unification algorithm by Qian has never been implemented due to its complexity AFAIK.</p>

CC BY-SA 3.0
2015-10-11T03:46:47.027Z
Luckily there are practical algorithms for it still. The handbook of automated reasoning says it can be done in polytime (right beside where it cites Qian's algorithm) so that's pretty awesome.
Jake
CC BY-SA 2.5
2011-01-24T13:46:32.450Z
2011-01-24T13:46:32.450Z
Dominic Mulligan
<p>Linear-time algorithm to check if a graph can be embedded in a fixed surface.</p>

<p>Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed: A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. FOCS 2008: 771-780.</p>

<p>Bojan Mohar: A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface. SIAM J. Discrete Math. 12(1): 6-26 (1999)</p>

CC BY-SA 2.5
2011-01-26T05:43:38.240Z
This is unlikely to have practical value even if implemented, due to the large exponential (sic) dependence on genus.
Jeffε
CC BY-SA 2.5
2011-01-23T22:16:34.723Z
2011-01-23T22:16:34.723Z
someone
<p>I'm not sure how useful it could be in practice (although I'm thinking about protein folding and comparison, as well as RNA secondary structure prediction), but Wolfgang Haken gave the first <strike>polynomial-time</strike> algorithm for deciding whether a knot is a simple loop (<em>Theorie der Normalflächen.</em> Acta Math. 105, 1961, pp. 245--375). As I recall, it is still too complicated to be implemented all those decades later.</p>

<p>If Wikipedia is to be believed, several other algorithms were later given, and "Understanding the complexity of these algorithms is an active field of study.".</p>

CC BY-SA 2.5
2011-01-27T14:45:36.787Z
Haken gave the first algorithm, but it does not run in polynomial time; in fact, no poly-time algorithm (or NP-hardness result) is known. More recent work has reduced knot triviality (via Haken's normal-surface formulation) to integer programming, which is usually quick to solve in practice.
Jeffε
CC BY-SA 2.5
2011-01-24T08:57:09.157Z
2011-01-27T15:54:16.113Z
2011-01-27T15:54:16.113Z
Anthony Labarre
<p>Tree decomposition<strike>, and perhaps Fibonacci heaps</strike>.</p>

CC BY-SA 2.5
2011-01-24T01:01:42.550Z
Fibonacci heaps are certainly not too complicated to implement; they have been implemented, and tested. The problem with them is rather that their practical performance is not as good as some other heaps due to largish constant factors in their running time.
David Eppstein
CC BY-SA 2.5
2011-01-24T02:39:52.517Z
That is a good point. I will modify my comment.
Peter Boothe
CC BY-SA 2.5
2011-01-24T02:53:50.527Z
I wrote a package to find tree decomposition, and I don't think it's hard to implement http://yaroslavvb.blogspot.com/2011/01/building-junction-trees.html
Yaroslav Bulatov
CC BY-SA 2.5
2011-01-24T03:29:45.133Z
The code you linked to finds a tree decomposition, but it does not find the optimal one (the one of width $k$, when given a $k$-tree).  By being short in my comment I was unclear - I was referring to the $O(n)$ algorithm for tree decomposition for a fixed tree width $k$.  Looking at your code, it looks like it produces a decomposition for a graph of unknown width - an NP complete problem.  Is this correct, or am I confused (quite likely, as I have extremely limited Mathematica experience)?
Peter Boothe
CC BY-SA 2.5
2011-01-24T03:48:10.877Z
My code is just a heuristic tree-decomposition, not optimal like branch-and-bound and dynamic programming approaches...I'm guessing you meant Bodlaender's "A Linear Time Algorithm ..."? I have not seen any implementations of that
Yaroslav Bulatov
CC BY-SA 2.5
2011-01-24T04:23:33.847Z
That is the one I meant! I also have never seen an implementation of it.
Peter Boothe
CC BY-SA 3.0
2011-06-10T08:52:07.780Z
Bodlaender's linear-time algorithm uses a dynamic-programming algorithm from an earlier paper as a subroutine: that algorithm computes an optimal treedecomposition in something like $2^{O(k^3)} O(n)$ time, when given an approximate-treedecomposition of width k as input. I think I recall that Hans Bodlaender once told me that they implemented this dynamic programming algorithm that is used as a subroutine, but it was already too slow for k=3. The dynamic programming is the main part of the linear-time algorithm, so Bodlaender's algorithm is not too hard to implement, just too slow.
Bart Jansen
CC BY-SA 3.0
2011-06-15T20:21:13.150Z
I think this is the best implementation effort: http://hein.roehrig.name/dipl/
didest
CC BY-SA 2.5
2011-01-23T22:18:56.213Z
2011-01-24T02:40:07.867Z
2011-01-24T02:40:07.867Z
Peter Boothe
<p>Perfect hash construction (<a href="https://en.wikipedia.org/wiki/Perfect_hash_function#Construction" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Perfect_hash_function#Construction</a>) would apply to any use-case with static or infrequently-changing keys (e.g. top level domain names on routers, keywords in compilers, or function names in standard libraries) but the last time I looked I couldn't find any implementations.</p>

<p>Parametric search can solve many difficult optimization problems, including some that might look like they should be NP-hard, in polynomial time. The well-named paper <a href="https://www.sciencedirect.com/science/article/pii/S0925772104000203" rel="nofollow noreferrer">Parametric search made practical</a> implements a variant of parametric search, but still I do not think it has been implemented in practical software.</p>

<p>The <a href="https://dl.acm.org/citation.cfm?id=147511" rel="nofollow noreferrer">optimal algorithm for line segment intersection by Chazelle and Edelsbrunner</a> finds all $k$ intersections of $n$ line segments in $O(n \log n + k)$ time, but is complex. CGAL is a sophisticated geometry algorithm library, but <a href="https://doc.cgal.org/latest/Arrangement_on_surface_2/index.html#title27" rel="nofollow noreferrer">implements a simpler algorithm</a> that is $O((n+k) \log n)$.</p>

CC BY-SA 4.0
2018-07-24T21:02:04.477Z
I refuse to believe that the FKS construction is too complex to implement. It's actually quite straightforward. Maybe not practical, but certainly not too complex to implement.
Sasho Nikolov
CC BY-SA 4.0
2018-07-24T17:51:35.967Z
2018-07-24T17:51:35.967Z
Kevin A. Wortman
<p>What are some algorithms of legitimate utility that are simply too complex to implement?</p>

<p>Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication algorithm (Coppersmith-Winograd), which is reasonable to implement but has a constant that makes it useless in practice. I'm looking for algorithms that could plausibly have practical value, but are so difficult to code that they have never been implemented, only implemented in extremely artificial settings, or only implemented for remarkably special-purpose applications.</p>

<p>Also welcome are near-impossible-to-implement algorithms that have good asymptotics but would likely have poor real performance.</p>

CC BY-SA 2.5
2011-01-23T01:31:01.583Z
making this CW, since it could be a long list.
Suresh Venkat
CC BY-SA 2.5
2011-01-23T21:52:40.843Z
Is there a metric for 'near-impossible-to-implement'?  Is there theory that defines it?
Ritwik Bose
CC BY-SA 2.5
2011-01-24T08:38:36.627Z
@Mechko, perhaps a lower bound on the size of the smallest Turing machine that outputs a description of a Turing machine that is an implementation of the algorithm. :)
Radu GRIGore
CC BY-SA 2.5
2011-01-24T10:12:48.587Z
@Radu GRIGore is this an accepted metric or one that ought to be developed?  I suppose that (for now) there is a simple, immovable line that defines 'meh, not worth it'... :D
Ritwik Bose
CC BY-SA 2.5
2011-01-24T18:45:36.113Z
I am interested by the suggestion that Coppersmith-Winograd is reasonable to implement. Has anyone ever seen an implementation written down even in high level pseudo-code and has anyone ever estimated the constants?
Simd
CC BY-SA 3.0
2013-02-04T18:54:30.653Z
much more on [galactic algorithms](http://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/) on liptons blog with misc criteria. note that "large constants" in the algorithm is one criteria. other criteria are that the optimal bound can be a very long-range asymptotic bound and lower ranges of data sizes behave more like other "not galactic" algorithms. etc
vzn
<ds.algorithms><ds.data-structures><big-list><implementation>
Powerful Algorithms too complex to implement
Elliot JJ
# Powerful Algorithms too complex to implement

(Asked by: username_0 on 2011-01-23)

What are some algorithms of legitimate utility that are simply too complex to implement?

Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication algorithm (Coppersmith-Winograd), which is reasonable to implement but has a constant that makes it useless in practice. I'm looking for algorithms that could plausibly have practical value, but are so difficult to code that they have never been implemented, only implemented in extremely artificial settings, or only implemented for remarkably special-purpose applications.

Also welcome are near-impossible-to-implement algorithms that have good asymptotics but would likely have poor real performance.

**Tags:** ds.algorithms, ds.data-structures, big-list, implementation
> **Comments:**
> **username_1**: making this CW, since it could be a long list.  
> **username_2**: Is there a metric for 'near-impossible-to-implement'?  Is there theory that defines it?  
> **username_3**: @Mechko, perhaps a lower bound on the size of the smallest Turing machine that outputs a description of a Turing machine that is an implementation of the algorithm. :)  
> **username_2**: @Radu GRIGore is this an accepted metric or one that ought to be developed?  I suppose that (for now) there is a simple, immovable line that defines 'meh, not worth it'... :D  
> **username_4**: I am interested by the suggestion that Coppersmith-Winograd is reasonable to implement. Has anyone ever seen an implementation written down even in high level pseudo-code and has anyone ever estimated the constants?  
> **username_5**: much more on [galactic algorithms](http://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/) on liptons blog with misc criteria. note that "large constants" in the algorithm is one criteria. other criteria are that the optimal bound can be a very long-range asymptotic bound and lower ranges of data sizes behave more like other "not galactic" algorithms. etc  

---

## 9 answers

### Answer by username_6 on 2011-01-23. Score: 36

Chazelle gave a linear time algorithm for [triangulating a simple polygon](http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf). Skiena wrote (p.575, Algorithm Design Manual) that it's "sufficiently hopeless to implement that it qualifies more as an existence proof"

> **Comments:**
> **username_12**: Does the algorithm have reasonable constants?  
> **username_7**: Is this the only known linear time algorithm for the problem?  
> **username_8**: @ThomasAhle I believe it is the only known deterministic linear time algorithm. Amato, Goodrich, and Ramos have a simpler randomized one: https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/linear%20time%20triangulation.pdf  
> **username_9**: Chazelle's linear time simple polygon triangulation algorithm, to my knowledge, has never been implemented and likely never will be because of it's complexity and also because constants are high so it won't be able to compete with alternatives in practice. Major theoretical achievement though. Ralph Boland  
> **username_10**: I'll ask again: Does the algorithm have reasonable constants?  
> **username_11**: @user1271772: I don't believe anybody has made a serious effort to figure out whether there's a version of Chazelle's algorithm with reasonable constants. Since there are several very simple $O(n\log n)$ algorithms with small constants, the amount of computation time it would save is clearly dwarfed by the enormous cost of programming it up. You probably never want to triangulate any polygons with more than a few hundred edges, and for this size it's hard to imagine it could beat the $O(n \log n)$ algorithms.  

---

### Answer by username_13 on 2011-01-23. Score: 32

The [Risch algorithm](http://en.wikipedia.org/wiki/Risch_algorithm) for computing elementary antiderivatives. According to Wikipedia, no software package is known to implement the full algorithm due to its complexity.

> **Comments:**
> **username_14**: Wikipedia also points out that this is not an algorithm but a semi-algorithm because it requires heuristics for solving the constant problem.  
> **username_15**: What is heuristics? Can you give some link to read more about it?  

---

### Answer by username_1 on 2011-01-23. Score: 24

Any algorithm that uses the Robertson-Seymour results to infer a "polytime" algorithm for things involving graphs that exclude a fixed minor is asking for trouble. The constant hidden in their result is "galactic".

> **Comments:**
> **username_16**: Is this also hard to implement or just has a huge constant?  
> **username_17**: Yes, this does not look like a good example. If I understand correctly, the question is about algorithms which could be practical (hence likely 'small' constants) but are just too complex to implement. Of course, the whole question is open to different interpretations :-)  
> **username_1**: The problem is the constant comes from the very large list of minors that one needs to exclude for a particular property. I don't know of any way to generate the desired list of excluded minors for a given property, so it's not just a scale issue .  
> **username_18**: For instance, we don't even know the list of excluded minors for graphs embeddable in the torus.  
> **username_16**: Interesting.  Perhaps this should be added to the answer...  
> **username_19**: The problem here seems deeper: there is no _effective_ way known to generate the list of minors, so this doesn't actually yield an algorithm at all.  Most minor-closed properties yield an infinite list of excluded minors, if one translates the logical expression directly.  The Robertson-Seymour Theorem (Wagner's Conjecture) tells us that a finite list of excluded minors is lurking inside that infinite list, but the theorem gives absolutely no help in actually finding them.   So Robertson-Seymour therefore usually leads to a pure existence proof.  
> **username_1**: isn't it therefore "too complex to implement" ? :)  
> **username_17**: @Suresh: I don't think the complexity is in question here. Whether the algorithm satisfies the question constraint of "could have practical value" is in doubt :-)  
> **username_20**: Isn't even compiling a single graph $H$ into the $O(n^3)$ algorithm to test for having $H$ as a minor an extremely difficult task?  Hasn't the full algorithm only been implemented once or something?  
> **username_10**: -1 because the constant is "galactic" and the question went through exceptional effort to request NOT giving such an algorithm.  

---

### Answer by username_12 on 2011-01-23. Score: 16

Dan Willard's ["A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time"](http://scholar.google.com/scholar?cluster=9370873690129514324) describes an algorithm for maintaining an ordered set in an array of size $O(n)$ with insertion and deletion in $O(\frac{\log^2 n}{B})$ worst-case time, where $B$ is the page size.

The paper is 55 pages long, and its conclusion notes several improvements to the constants that the author does not describe for reasons of space. This makes me suspect that perhaps the constants aren't so galactic, and that this data structure would be of "legitimate utility", especially since it has been cited many times.


---

### Answer by username_21 on 2011-01-24. Score: 13

The linear time higher-order pattern unification algorithm by Qian has never been implemented due to its complexity AFAIK.

> **Comments:**
> **username_22**: Luckily there are practical algorithms for it still. The handbook of automated reasoning says it can be done in polytime (right beside where it cites Qian's algorithm) so that's pretty awesome.  

---

### Answer by username_23 on 2011-01-23. Score: 11

Linear-time algorithm to check if a graph can be embedded in a fixed surface.

Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed: A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. FOCS 2008: 771-780.

Bojan Mohar: A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface. SIAM J. Discrete Math. 12(1): 6-26 (1999)

> **Comments:**
> **username_24**: This is unlikely to have practical value even if implemented, due to the large exponential (sic) dependence on genus.  

---

### Answer by username_25 on 2011-01-24. Score: 8

I'm not sure how useful it could be in practice (although I'm thinking about protein folding and comparison, as well as RNA secondary structure prediction), but Wolfgang Haken gave the first polynomial-time algorithm for deciding whether a knot is a simple loop (*Theorie der Normalflächen.* Acta Math. 105, 1961, pp. 245--375). As I recall, it is still too complicated to be implemented all those decades later.

If Wikipedia is to be believed, several other algorithms were later given, and "Understanding the complexity of these algorithms is an active field of study.".

> **Comments:**
> **username_24**: Haken gave the first algorithm, but it does not run in polynomial time; in fact, no poly-time algorithm (or NP-hardness result) is known. More recent work has reduced knot triviality (via Haken's normal-surface formulation) to integer programming, which is usually quick to solve in practice.  

---

### Answer by username_26 on 2011-01-23. Score: 3

Tree decomposition, and perhaps Fibonacci heaps.

> **Comments:**
> **username_27**: Fibonacci heaps are certainly not too complicated to implement; they have been implemented, and tested. The problem with them is rather that their practical performance is not as good as some other heaps due to largish constant factors in their running time.  
> **username_26**: That is a good point. I will modify my comment.  
> **username_6**: I wrote a package to find tree decomposition, and I don't think it's hard to implement http://yaroslavvb.blogspot.com/2011/01/building-junction-trees.html  
> **username_26**: The code you linked to finds a tree decomposition, but it does not find the optimal one (the one of width $k$, when given a $k$-tree).  By being short in my comment I was unclear - I was referring to the $O(n)$ algorithm for tree decomposition for a fixed tree width $k$.  Looking at your code, it looks like it produces a decomposition for a graph of unknown width - an NP complete problem.  Is this correct, or am I confused (quite likely, as I have extremely limited Mathematica experience)?  
> **username_6**: My code is just a heuristic tree-decomposition, not optimal like branch-and-bound and dynamic programming approaches...I'm guessing you meant Bodlaender's "A Linear Time Algorithm ..."? I have not seen any implementations of that  
> **username_26**: That is the one I meant! I also have never seen an implementation of it.  
> **username_28**: Bodlaender's linear-time algorithm uses a dynamic-programming algorithm from an earlier paper as a subroutine: that algorithm computes an optimal treedecomposition in something like $2^{O(k^3)} O(n)$ time, when given an approximate-treedecomposition of width k as input. I think I recall that Hans Bodlaender once told me that they implemented this dynamic programming algorithm that is used as a subroutine, but it was already too slow for k=3. The dynamic programming is the main part of the linear-time algorithm, so Bodlaender's algorithm is not too hard to implement, just too slow.  
> **username_29**: I think this is the best implementation effort: http://hein.roehrig.name/dipl/  

---

### Answer by username_30 on 2018-07-24. Score: 1

Perfect hash construction (<https://en.wikipedia.org/wiki/Perfect_hash_function#Construction>) would apply to any use-case with static or infrequently-changing keys (e.g. top level domain names on routers, keywords in compilers, or function names in standard libraries) but the last time I looked I couldn't find any implementations.

Parametric search can solve many difficult optimization problems, including some that might look like they should be NP-hard, in polynomial time. The well-named paper [Parametric search made practical](https://www.sciencedirect.com/science/article/pii/S0925772104000203) implements a variant of parametric search, but still I do not think it has been implemented in practical software.

The [optimal algorithm for line segment intersection by Chazelle and Edelsbrunner](https://dl.acm.org/citation.cfm?id=147511) finds all $k$ intersections of $n$ line segments in $O(n \log n + k)$ time, but is complex. CGAL is a sophisticated geometry algorithm library, but [implements a simpler algorithm](https://doc.cgal.org/latest/Arrangement_on_surface_2/index.html#title27) that is $O((n+k) \log n)$.

> **Comments:**
> **username_8**: I refuse to believe that the FKS construction is too complex to implement. It's actually quite straightforward. Maybe not practical, but certainly not too complex to implement.  

---

