Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Concrete minkowski difference for hyperrectangular sets #1721

Closed
mforets opened this issue Sep 22, 2019 · 0 comments · Fixed by #3269
Closed

Concrete minkowski difference for hyperrectangular sets #1721

mforets opened this issue Sep 22, 2019 · 0 comments · Fixed by #3269
Assignees
Labels
good first issue 🐤 Good for newcomers performance 🐎 More efficient code

Comments

@mforets
Copy link
Member

mforets commented Sep 22, 2019

The implementation of concrete minkowski difference for polytopic sets can be specialized to axis-aligned (= hyperrectangular sets in our notation) sets.

Sketch:
since they are hyperrectangular sets => their directions are parallel

P ~ Q = \\{z ∈ ℝⁿ: sᵢᵀz ≤ rᵢ - ρ(sᵢ,Q), i=1,...,N\\}.

the normal directions of P⊖Q are also axis aligned
it remains to evaluate rᵢ - ρ(sᵢ,Q) for all i
(assume that the hyperrectangles are centered to the origin => both are obtained iirc with radius_hyperrectangle(H, i))
moreover, we can have an early termination to check that the minkowski difference is empty by computing the pairs of right hand sides +ei and -ei for each i

@mforets mforets added the performance 🐎 More efficient code label Sep 22, 2019
@mforets mforets added the good first issue 🐤 Good for newcomers label Apr 12, 2020
@schillic schillic self-assigned this Apr 6, 2023
schillic added a commit that referenced this issue Apr 30, 2023
#1721 - Concrete minkowski difference for hyperrectangular sets
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
good first issue 🐤 Good for newcomers performance 🐎 More efficient code
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants