# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Sat, 25 May 2013 14:57:30 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 2 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Determine if a rectangular solid is within polyhedron?Posted: Fri, 1 Apr 2011 15:52:41 UTC
 Member of the 'S.O.S. Math' Hall of Fame

Joined: Tue, 20 Nov 2007 04:36:12 UTC
Posts: 826
Location: Las Cruces
Find an efficient set of constraints that determine whether an axis-aligned rectangular solid is inside a polyhedron. Be more economical than writing constraints that say each corner of the rectangular solid is inside it.

I found a solution to this problem on the web, but there was no proof of the answer. Can anyone explain why the following constraints would work?

Let and be dimensional vectors with ( The "" means a component-by-component relation.) Let be the rectangular solid defined by the vectors (So is the "lower corner" and is the "upper" corner). Let be the polyhedron defined by the set of vectors
where is a given matrix with row entries and is a given vector of the same column dimension as .

Define to be the matrix with entries .

Define to be the matrix with entries .

iff

Top

 Post subject: Re: Determine if a rectangular solid is within polyhedron?Posted: Fri, 1 Apr 2011 16:46:59 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6009
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
tashirosgt wrote:
Find an efficient set of constraints that determine whether an axis-aligned rectangular solid is inside a polyhedron. Be more economical than writing constraints that say each corner of the rectangular solid is inside it.

I found a solution to this problem on the web, but there was no proof of the answer. Can anyone explain why the following constraints would work?

Let and be dimensional vectors with ( The "" means a component-by-component relation.) Let be the rectangular solid defined by the vectors (So is the "lower corner" and is the "upper" corner). Let be the polyhedron defined by the set of vectors
where is a given matrix with row entries and is a given vector of the same column dimension as .

Define to be the matrix with entries .

Define to be the matrix with entries .

iff

I think you want instead of the other way round (otherwise your cuboid is empty).

The left hand side of each constraint is the largest possible as v ranges over the vertices , by the choice of A^+ and A^- (if the coefficient is negative, choose the lower so it subtracts less, and if the coefficient is positive, choose the upper so it adds more).

_________________

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 2 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous