Opened 5 years ago
Last modified 5 years ago
#24451 closed enhancement
Polyhedron.get_integral_point — at Version 8
Reported by:  Mark Bell  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  geometry  Keywords:  Polyhedron, integral_points 
Cc:  Vincent Delecroix, Thierry Monteil, Matthias Köppe  Merged in:  
Authors:  Mark Bell  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/mcbell/polyhedron_get_integral_point (Commits, GitHub, GitLab)  Commit:  82a64d2f6eb533c16413c681a8d89c130283fa1c 
Dependencies:  Stopgaps: 
Description (last modified by )
This patch adds a method Polyhedron.get_integral_point(index) which returns the nth integral point in the polyhedron. It is equivalent to sorted(Polyhedron.integral_points())[index]. However when Polyhedron.integral_points_count() does not need to enumerate all of the integral points, for example in rational Polyhedra, neither does this method. Hence it can be significantly faster.
This method is useful for performing random sampling of integral points since it allows points to be chosen uniformly at random via:
index = randint(0, P.integral_points_count()) point = P.get_integral_point(index)
Change History (8)
comment:1 Changed 5 years ago by
Branch:  → u/mcbell/polyhedron_get_integral_point 

comment:2 Changed 5 years ago by
Authors:  → Mark Bell 

Cc:  Vincent Delecroix Thierry Monteil Matthias Köppe added 
Commit:  → d3b9b396c1dc9d6ca8c9478b01035454ebbe1f74 
Component:  PLEASE CHANGE → geometry 
Description:  modified (diff) 
Keywords:  Polyhedron integral_points added 
Status:  new → needs_review 
Type:  PLEASE CHANGE → enhancement 
comment:3 Changed 5 years ago by
comment:4 followup: 5 Changed 5 years ago by
Sure, that would be a simple enough thing to change  should I open a new ticket?
comment:5 followup: 7 Changed 5 years ago by
Replying to mcbell:
Sure, that would be a simple enough thing to change  should I open a new ticket?
Though, I do not think I was right: e.g. integral points are naturally indexed for the lexicographical ordering. In the description, you claim to follow the ordering of integral_points
. Is it always lexicographic? I could not find any mention of ordering in the documentation. Note in particular that integral_points
claims to have two implementations
Uses either the naive algorithm (iterate over a rectangular bounding box) or triangulation + Smith form.
The ordering is independent of the method?
BTW, your branch u/mcbell/polyhedron_get_integral_point
does not exist. Is that normal?
About get_integral_point
vs random_integral_point
you are free to do whatever you want with your ticket :)
comment:6 Changed 5 years ago by
Commit:  d3b9b396c1dc9d6ca8c9478b01035454ebbe1f74 → 82a64d2f6eb533c16413c681a8d89c130283fa1c 

Branch pushed to git repo; I updated commit sha1. New commits:
e020df5  Initial version of get_integral_point method.

ca57e15  Added docstring and more comments.

f771506  Fixed docstring whitespace.

626e399  Fixed line widths and fencepost error in upper bound.

c46460d  Added sorting comments to docstring and random_integral_point method.

82a64d2  Added missing import.

comment:7 Changed 5 years ago by
Replying to vdelecroix:
Thanks for the great comments. I think I've now managed to push my branch onto trac so you should be able to see the code.
Though, I do not think I was right: e.g. integral points are naturally indexed for the lexicographical ordering. In the description, you claim to follow the ordering of
integral_points
. Is it always lexicographic? I could not find any mention of ordering in the documentation. Note in particular thatintegral_points
claims to have two implementationsUses either the naive algorithm (iterate over a rectangular bounding box) or triangulation + Smith form.The ordering is independent of the method?
Ah, you are correct, you are not guaranteed to get lexicographical ordering when the triangulation method is used. In part this is caused by the fact that the points that are found in the different triangles are just merged together using a set. Perhaps L5288 of src/sage/geometrypolyhedron/base.py should become "return tuple(sorted(points))" to make the method deterministic. So the correct thing to say is that this method returns
sorted(self.integral_points())[index]
I've updated the docstring and above explanation to reflect this.
My new suggestion, which is in the latest commits, is to also add a Polyhedron.random_integral_point() method that just uses the snippet I posted originally.
comment:8 Changed 5 years ago by
Description:  modified (diff) 

Mark,
As we discussed in Warwick, this method is rather unnatural (integer points are not naturally indexed) and is not needed for random sampling. To my mind, it would make more sense to have a new method
.random_integral_point
implemented along the same lines.