0
$\begingroup$

I have a piece of code which finds all triangulations of a convex polygon. It is known that a number of such triangulations for a given $n$-gon is is given by ($n-2$)th Catalan Number, so for instance, for a pentagon, there are 5 triangulations:

CatalanNumber[3]

5

enter image description here

So, for instance, if I try to find all the triangulations of a 15-gon and there 742900 of them, everything is fine. It takes about 3 minutes to find them but it works. But, for instance, if I try to do it for a 20-gon (there are 477638700 triangulations), it will run for about 20 minutes before it stops. It stops, with no errors, but when I try to look at the list of triangulations there is nothing there, it appears that the notebook restarted(?) itself. Is that a memory issue? Can that be handled in Mathematica? What if I wanted to find all triangulations of a 100-gon (there are 57743358069601357782187700608042856334020731624756611000 such triangulations)?? What would be the biggest issue there? Memory? Storage?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ "Is that a memory issue?" It could be. Use a process monitor to watch the memory usage of the WolframKernel process. "What if I wanted to find all triangulations of a 100-gon" Then you'd be out of luck. Combinatorial explosion is a common computational obstacle. Time and memory both limit what can be done. Have you estimated how much memory it would take to store all these triangulations, and then search for how much memory the biggest supercomputers have? $\endgroup$
    – Szabolcs
    May 22, 2019 at 9:49
  • $\begingroup$ I am not meaning to be dismissive but I am leaning towards voting to close as "asking for the obviously impossible". (This assessment is not specific to Mathematica.) One might potentially find a reasonable question here by limiting the problem to reasonable sizes which seem to be almost in reach for Mathematica ... then we can discuss how you can do something specifically in Mathematica that could otherwise be done without problems e.g. in C. $\endgroup$
    – Szabolcs
    May 22, 2019 at 9:51
  • $\begingroup$ @Szabolcs thank you for your comment! Feel free to close the question since as you pointed out, at this stage, I don't think there is much more to be said. $\endgroup$
    – amator2357
    May 22, 2019 at 10:02
  • 2
    $\begingroup$ When memory is an issue it is often useful to think about whether you actually need to keep all of them in memory. Not all problems require that. $\endgroup$
    – Szabolcs
    May 22, 2019 at 10:44
  • 1
    $\begingroup$ Even if one stored a triangualation in a single bit (which is of course impossible), you would still need UnitConvert[ N@Quantity[57743358069601357782187700608042856334020731624756611000, "Bits"], "Gigabytes" ] memory. That is about 7 10^45 Gigabytes. Out of reach. $\endgroup$
    – Henrik Schumacher
    May 22, 2019 at 11:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.