Computing triangulations fails
Hello everyone,
I hope this is the correct place to report a possible bug, sorry if I should have reported elsewhere.
I ran into some trouble with a sage function computing triangulations.
To give you an example, the following code does not seem to terminate on my work computer (and it makes Sage crash on my personal computer or on online sage servers due to the lack of ram (4 or 8GB)).
PointConfiguration.set_engine('internal');
points = [[64374, 1170],[28595,16],[1162, 658], [28874, 3308], [29974, 9436], [30590, 22299], [49434, 11393], [56042, 11982], [42392, 33338], [33404, 64878]];
p = PointConfiguration(points);
p_fine = p.restrict_to_fine_triangulations();
list_triangulations = list(p_fine.triangulations()) #does not seem to terminate in a reasonable amount of time
On my computer, it seems that the iterator p_fine.triangulations() is able to compute the first 1477 triangulations (out of 2002 triangulations), but fails to compute the 1478th. The points are in generic position, in the sense that the points are pairwise distinct and no three points are aligned.
To give you more context, I tested the triangulations() method on many configurations of 10 points coming from the database of order points available on Oswin Aichholzer's website (I do not have enough karma to publish a link). That is how I found several configurations for which the iterator computing fine triangulations seemed to not terminate (or at least take an excessive amount of memory and time).
Best regards,
Florent
I can confirm I have the same issue on
SageMath version 10.2:@fkoechlinhttps://ask.sagemath.org/ is indeed a possible place for end users to report issues. Such questions can be tagged https://ask.sagemath.org/questions/sc... one the issue is confirmed and reported and https://ask.sagemath.org/questions/sc... once the issue is fixed.
@Sebastien i do not have a github account to do that myself.
@both it is not clear that there is a bug here. I did not look at the source code, but if it relies on some backtracking algorithm, it is frequent that at after exploring a prolific part of the tree, the algorithm has to explore a huge branch that does not provide anything interesting. I saw that behaviour in some other context.
How long did you wait ?
In my case, on my recent laptop, it's not me that kills it. The operation kills itself after less than 1 second.
On my older machine, the computation hangs and mentions a memory issue:
I created issue #38187 on github
Hi, sorry for the delay, as I was at a conference I forgot to check the notifications.
@tmonteil I had two possible behaviours : either sage gets killed automatically (on my current old laptop), or the program uses a huge amount of ram and seems to loop (on my postdoc computer that I do no have anymore). I don't remember how long I waited, but I think I waited at least one hour. I cannot reproduce it for the moment as with my current laptop sage gets killed after a few seconds.
@Sébastien Thank you for handling the report on github!