Timeline for Powerful Algorithms too complex to implement
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 24, 2018 at 22:11 | comment | added | Peter Shor | @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. | |
| May 2, 2017 at 20:03 | comment | added | user1271772 | I'll ask again: Does the algorithm have reasonable constants? | |
| Oct 11, 2015 at 2:01 | comment | added | Ralph Boland | 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 | |
| Feb 20, 2014 at 21:41 | comment | added | Sasho Nikolov | @ThomasAhle I believe it is the only known deterministic linear time algorithm. Amato, Goodrich, and Ramos have a simpler randomized one: cs.princeton.edu/courses/archive/fall05/cos528/handouts/… | |
| Nov 17, 2013 at 22:17 | comment | added | Thomas Ahle | Is this the only known linear time algorithm for the problem? | |
| Jan 25, 2011 at 8:01 | comment | added | jbapple | Does the algorithm have reasonable constants? | |
| Jan 24, 2011 at 2:52 | history | edited | Yaroslav Bulatov | CC BY-SA 2.5 |
deleted 15 characters in body
|
| Jan 23, 2011 at 3:24 | history | edited | Abel Molina | CC BY-SA 2.5 |
Spelling of Chazelle
|
| S Jan 23, 2011 at 3:05 | history | answered | Yaroslav Bulatov | CC BY-SA 2.5 | |
| S Jan 23, 2011 at 3:05 | history | made wiki | Post Made Community Wiki |