Opened 5 years ago

Closed 7 weeks ago

#17215 closed enhancement (fixed)

Normal cone of faces of polyhedra

Reported by: darij Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: polytopes, linear programming, linear optimization, days100
Cc: gh-LaisRast, gh-kliem, chapoton, nailuj Merged in:
Authors: Jean-Philippe Labbé Reviewers: Jonathan Kliem
Report Upstream: N/A Work issues:
Branch: 7278f23 (Commits) Commit: 7278f23b2bd3178fd399d05d7fd171d808c9f834
Dependencies: #29155 Stopgaps:

Description (last modified by jipilab)

A point v on a convex polyhedron P is a vertex of P if and only if there exists an affine hyperplane in the linear span of P which intersects P only in v. Knowing such affine hyperplane is a good certificate for v being a vertex.

This ticket implements the method normal_cone for faces of polyhedra, consisting of all the directions of the normals to supporting hyperplanes of the specified face.

Change History (39)

comment:1 Changed 5 years ago by darij

  • Description modified (diff)
  • Summary changed from Normal vector to a polyhedron at a point... to Normal vector to a polyhedron at a face...

comment:2 Changed 5 years ago by darij

  • Description modified (diff)
  • Summary changed from Normal vector to a polyhedron at a face... to Bounding lines for polyhedra

comment:3 Changed 5 years ago by darij

  • Description modified (diff)
  • Summary changed from Bounding lines for polyhedra to Bounding hyperplanes for polyhedra

comment:4 Changed 5 years ago by darij

  • Description modified (diff)

comment:5 Changed 5 years ago by vbraun

All backends right now compute both H/V-representation; the dual is of course a much more complete certificate that a vertex is really a vertex. Also, the bounding hyperplane is not canonical---which one to pick? If you really need one you can construct one from the incident hyperplane equations of the vertex (or, more generally, d-dimensional face).

sage: P = polytopes.n_cube(3)
sage: v = P.vertices()[0]
sage: v
A vertex at (-1, -1, -1)
sage: A = sum(h.A() for h in v.incident())
sage: b = sum(h.b() for h in v.incident())
sage: b, A
(3, (1, 1, 1))
sage: Polyhedron(eqns=[[b] + list(A)]) & P
A 0-dimensional polyhedron in QQ^3 defined as the convex hull of 1 vertex

comment:6 Changed 5 years ago by darij

Thanks, this makes it a lot easier.

comment:7 Changed 3 years ago by moritz

  • Status changed from new to needs_info

Should this remain open?

comment:8 Changed 3 years ago by jipilab

Not sure... perhaps there could be a method in the class for polyhedron_faces giving the corresponding normal cone?

comment:9 Changed 10 months ago by gh-kliem

To my understanding such a method for each face of a Polyhedron would also help #27973, such that one could construct a wedge over a face (not just a facet).

comment:10 Changed 9 months ago by jipilab

  • Component changed from combinatorics to geometry
  • Description modified (diff)
  • Keywords days100 added
  • Milestone changed from sage-6.4 to sage-8.9
  • Status changed from needs_info to needs_work
  • Summary changed from Bounding hyperplanes for polyhedra to Supporting cone & normal cone of faces of polyhedra

comment:11 Changed 9 months ago by jipilab

  • Authors set to Jean-Philippe Labbé
  • Branch set to u/jipilab/17215
  • Cc gh-LaisRast gh-kliem chapoton added
  • Commit set to 302ec4609ea007b9c89001b91b1890961e535274
  • Dependencies set to #27973

New commits:

302ec46First version

comment:12 Changed 8 months ago by jipilab

  • Cc nailuj added
  • Summary changed from Supporting cone & normal cone of faces of polyhedra to Normal cone of faces of polyhedra
  • Type changed from task to enhancement

comment:13 follow-up: Changed 8 months ago by gh-kliem

If you construct the polyhedron with via the_poly.parent() similar to e.g. many examples in #27926 you can avoid the import of the constructor.

Don't know if that's better.

comment:14 in reply to: ↑ 13 Changed 8 months ago by jipilab

Replying to gh-kliem:

If you construct the polyhedron with via the_poly.parent() similar to e.g. many examples in #27926 you can avoid the import of the constructor.

Don't know if that's better.

Yes, might be cleaner yes...

comment:15 Changed 8 months ago by git

  • Commit changed from 302ec4609ea007b9c89001b91b1890961e535274 to 2f8e3a95d9c4d2eac294ba40491427d7a81d7c16

Branch pushed to git repo; I updated commit sha1. New commits:

2f8e3a9Changed to use parent

comment:16 Changed 8 months ago by jipilab

Now, only waiting for the wedge to get merged. After that, I would change some constructions to make use of this new function to deduplicate some code...

comment:17 Changed 5 months ago by jipilab

  • Branch changed from u/jipilab/17215 to u/jipilab/17215rebsed
  • Commit changed from 2f8e3a95d9c4d2eac294ba40491427d7a81d7c16 to 12581fd5b643d482bd0ba66fbd32d845ca8df035
  • Status changed from needs_work to needs_review

I decided to leave the wedge and face truncation construction as they are since they do not need an explicit polyhedron.


New commits:

02f1417First version
aa8d87eChanged to use parent
477f73ffixed tests
12581fdreverted changes on truncations

comment:18 Changed 5 months ago by gh-kliem

  • Status changed from needs_review to needs_work

You did not consider the case, where the polyhedron has equations.

In this case your considering one of two possible rays. Probably should only append rays for inequalities, but I'm not sure.

One question: How do we construct the hyperplane that interesects exactly the face from this (see description of ticket).

comment:19 Changed 5 months ago by gh-kliem

  • Dependencies changed from #27973 to #27973, #28646

#28646 changes the order of faces, which affects a doctest in this ticket.

comment:20 Changed 3 months ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:21 Changed 2 months ago by jipilab

  • Branch changed from u/jipilab/17215rebsed to u/jipilab/17215reb2
  • Commit changed from 12581fd5b643d482bd0ba66fbd32d845ca8df035 to 2f114d8e76529192f5879b75c5a368f0b1acc010
  • Status changed from needs_work to needs_review

New commits:

2f114d8First version

comment:22 Changed 2 months ago by jipilab

Rebased due to conflict. Needs review.

comment:23 Changed 2 months ago by gh-LaisRast

  • Status changed from needs_review to needs_work

You put the method under the function combinatorial_face_to_polyhedral_face. You need to change its location. Otherwise it is not accessible.

comment:24 Changed 2 months ago by git

  • Commit changed from 2f114d8e76529192f5879b75c5a368f0b1acc010 to 4b803a144fc01e1a4336421b0343dbeec310c789

Branch pushed to git repo; I updated commit sha1. New commits:

4b803a1moved back the method

comment:25 Changed 2 months ago by jipilab

  • Status changed from needs_work to needs_review

comment:26 follow-up: Changed 2 months ago by gh-LaisRast

  • Status changed from needs_review to needs_work

I changed it to "needs_work" because it still does not work for non-full-dimensional polytopes.

On a (very) related topic, the method normal_fan of Polyhedron returns

ValueError: the normal fan is only defined for full-dimensional polytopes

for non-full-dimensional polytopes. It should return "not implemented" since normal_fan is defined for non-full-dimensional polytopes.

comment:27 Changed 2 months ago by git

  • Commit changed from 4b803a144fc01e1a4336421b0343dbeec310c789 to 31906994cfeaa60abca4df9970edea2ce183ae8a

Branch pushed to git repo; I updated commit sha1. New commits:

3190699fixed construction normal cone

comment:28 Changed 2 months ago by jipilab

  • Status changed from needs_work to needs_review

comment:29 in reply to: ↑ 26 Changed 2 months ago by jipilab

Replying to gh-LaisRast:

I changed it to "needs_work" because it still does not work for non-full-dimensional polytopes.

On a (very) related topic, the method normal_fan of Polyhedron returns

ValueError: the normal fan is only defined for full-dimensional polytopes

for non-full-dimensional polytopes. It should return "not implemented" since normal_fan is defined for non-full-dimensional polytopes.

This should be addressed in a different ticket...

comment:30 follow-up: Changed 2 months ago by gh-kliem

  • Dependencies changed from #27973, #28646 to #29155

Reading carefully your doctests, one sees a bug, which will be fixed in #29155.

Instead of using faces for iteration you can use the new method face_generator.

comment:31 in reply to: ↑ 30 Changed 2 months ago by jipilab

Replying to gh-kliem:

Reading carefully your doctests, one sees a bug, which will be fixed in #29155.

Aa ha!! I see I was also somehow confused by that, but did not think more about it.

Instead of using faces for iteration you can use the new method face_generator.

Good suggestion.

comment:32 Changed 8 weeks ago by git

  • Commit changed from 31906994cfeaa60abca4df9970edea2ce183ae8a to 060d2b38b49d99a787c2468c58a757f8656d6bc1

Branch pushed to git repo; I updated commit sha1. New commits:

7c35b0eface to face_generator
d7f47adinitialize full-dimensional face with equations
e55569aMerge branch 'public/29155' of trac.sagemath.org:sage into 17215
060d2b3fixed doctest

comment:33 Changed 8 weeks ago by gh-kliem

  • Reviewers set to Jonathan Kliem
  • Status changed from needs_review to needs_work

I think the following is more direct:

-        origin = parent.zero().vertices()[0].vector()
+        origin = self.ambient_space().zero()

Otherwise you can put it positive review on my behalf. Maybe wait for bots yet.

comment:34 Changed 8 weeks ago by git

  • Commit changed from 060d2b38b49d99a787c2468c58a757f8656d6bc1 to 77d87d5ff776dad45d805318090e380d483cfb4c

Branch pushed to git repo; I updated commit sha1. New commits:

77d87d5fixed origin def

comment:35 Changed 8 weeks ago by jipilab

  • Status changed from needs_work to needs_review

comment:36 Changed 8 weeks ago by git

  • Commit changed from 77d87d5ff776dad45d805318090e380d483cfb4c to 7278f23b2bd3178fd399d05d7fd171d808c9f834

Branch pushed to git repo; I updated commit sha1. New commits:

7278f23fixed doctest

comment:37 Changed 8 weeks ago by jipilab

There was an error... ambient_space doesn't exist for faces... So I fixed it.

comment:38 Changed 8 weeks ago by gh-kliem

  • Status changed from needs_review to positive_review

LGTM. Note that #28880 fixes the pyflakes warning.

comment:39 Changed 7 weeks ago by vbraun

  • Branch changed from u/jipilab/17215reb2 to 7278f23b2bd3178fd399d05d7fd171d808c9f834
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.