search

JuliaReach / LazySets.jl

Scalable symbolic-numeric set computations in Julia
https://juliareach.github.io/LazySets.jl/
Other
226 stars 32 forks source link

Add interval arithmetic set type in higher dimensions #302

Open schillic opened 6 years ago

schillic commented 6 years ago

This is basically the generalization of Interval for higher dimensions. See IntervalBox.

mforets commented 5 years ago

Do we want to add this as a new set type or to be able to convert back and forth between IntervalBox and Hyperrectangle? I think that the latter is OK.

schillic commented 5 years ago

Yeah, I would say that we should add a new type (possibly also called IntervalBox). Otherwise we would have to change all implementations, because IntervalArithmetic.IntervalBox represents the set as a vector of Intervals.

mforets commented 5 years ago

to be able to convert back and forth between IntervalBox and Hyperrectangle? I think that the latter is OK.

this conversion was added in LazySets v1.0.0

Do we want to add this as a new set type

being a different representation than Hyperrectangle, as it is seen in the link you posted, for some operations there are certainly cases where one is better than the other (performance-wise), but i haven't instigated too much. for support function computations it is better to have the center and radius representation though.

schillic commented 5 years ago

for support function computations it is better to have the center and radius representation though.

I am not sure. You have to look at the sign of each dimension and take the upper/lower bound respectively. With center/radius you have to compute this bound, while if you store the intervals you can just look up the number. So I would guess that the intervals are actually cheaper.

mforets commented 5 years ago

one still has to compute the sign of di to see if one has to muliplied by either the inf or the sup. indeed computing the differences c[i] - radius_hyperrectangle(H, i) and c[i] + radius_hyperrectangle(H, i) seems to be avoided.

mforets commented 4 years ago

So I would guess that the intervals are actually cheaper.

you're right -- i played a bit and the version with intervals is faster for low dimensions (there is a crossover somewhere between 20 and 40)

mforets commented 2 years ago

What would be a good name? Hypercube?

cc: @asarvind

schillic commented 2 years ago

No, Hypercube would be a BallInf.

We could just call it IntervalBox and get another name clash. Or HyperrectangleB (B for bounds) or Hyperbox.

No matter how we call it, having a second set type may cause confusion with Hyperrectangle (which type should you use?). Since the structs would have the same signature (store two vectors of length n), we could also modify Hyperrectangle by adding a type parameter Val{true}/Val{false} such that if it is false, it interprets center as lower bound and radius as upper bound (ideally we would rename the fields and always use helper functions to obtain center/radius/low/high, but that might break a lot of code).

mforets commented 2 years ago

How about Hypercuboid?

schillic commented 2 years ago

Summary of a discussion: