Opened 9 years ago

Closed 9 years ago

#10238 closed defect (fixed)

Containment checks are wrong for empty polyhedra

Reported by: novoselt Owned by: mhampton
Priority: major Milestone: sage-4.6.1
Component: geometry Keywords:
Cc: vbraun, novoselt Merged in: sage-4.6.1.alpha1
Authors: Volker Braun Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

sage: p = Polyhedron()
sage: p
The empty polyhedron in QQ^0.
sage: p.contains(0)
True
sage: p.contains(1)
True
sage: p.contains([0, 1])
True
sage: p.contains([(0, 1)])
True
sage: p.interior_contains([0, 1])
True
sage: p.relative_interior_contains([0, 1])
True

I think all of the above should return False.

Attachments (1)

trac_10238_containment_check_for_empty_polyhedra.patch (8.3 KB) - added by vbraun 9 years ago.
Updated patch

Download all attachments as: .zip

Change History (10)

comment:1 follow-up: Changed 9 years ago by vbraun

  • Cc novoselt added
  • Status changed from new to needs_review

I changed the "empty" polyhedron to contain one equation 0==-1. I also modified the "contains" checks to be slightly more general and work with points whose coordinates are not necessarily in the same field as the polyhedron.

comment:2 in reply to: ↑ 1 Changed 9 years ago by novoselt

  • Status changed from needs_review to needs_work

Replying to vbraun:

I changed the "empty" polyhedron to contain one equation 0==-1.

This seems reasonable, but it shows in the doctest as "[An equation () x + -1 == 0]" which is confusing: what is "() x" and why "+ -"?

This is not directly related to this ticket, but how about omitting "() x +" for 0-dimensional equations/inequalities and taking into account the "+ -" situation in general?

comment:3 Changed 9 years ago by novoselt

  • Authors set to Volker Braun
  • Reviewers set to Andrey Novoseltsev

comment:4 Changed 9 years ago by vbraun

  • Status changed from needs_work to needs_review

I guess this ticket is as good as any other to fix the string '_repr_()' of (in)equalities :-) The updated patch skips "zero coefficient times x" and handles the sign of the constant term nicer.

comment:5 Changed 9 years ago by novoselt

  • Status changed from needs_review to needs_info

Patch order issues:

applying trac_10238_containment_check_for_empty_polyhedra.patch
patching file sage/geometry/polyhedra.py
Hunk #8 succeeded at 4208 with fuzz 2 (offset 446 lines).
now at: trac_10238_containment_check_for_empty_polyhedra.patch

(Tested on top of face lattice.)

I am fine with this version, but just to make sure: you really want to start the line with "+" if there are no variables and have space between the sign and the coefficient only if there are variables?

comment:6 Changed 9 years ago by vbraun

I rearranged the patches an in #9604, should apply cleanly now.

My preferred prettyprinting is

  An equation (-1) x + 1 >= 0
  An equation (2) x - 1 >= 0
  An equation 1 == 0
  An equation -1 == 0

and I fixed the 3rd one in the patch.

Changed 9 years ago by vbraun

Updated patch

comment:7 Changed 9 years ago by novoselt

  • Status changed from needs_info to needs_review

Cool!

comment:8 Changed 9 years ago by novoselt

  • Status changed from needs_review to positive_review

comment:9 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.6.1.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.