gaperez64 / acacia-bonsai

A minimal implementation of reactive synthesis via universal co-Buchi automata using antichains
GNU General Public License v3.0
4 stars 3 forks source link

kd-tree updates and logarithmic method #42

Closed gaperez64 closed 8 months ago

gaperez64 commented 9 months ago

I started implementing the new kd-tree building and querying algorithms. Two things are missing on the kd-tree front:

  1. The trim procedure which will be used when implementing the logarithmic method data structure
  2. Updated iteration through the elements of the tree, taking into account removed/dirty nodes. Both of the above are marked in the code as TODOs
gaperez64 commented 9 months ago

One thought about item 2.

Perhaps the easiest is to keep a vector with the nonremoved elements and use it as a cache that is dropper after every trim operation that does remove at least one node?

gaperez64 commented 9 months ago

The kd-tree structure is now fully updated. Moving on to implementing the logarithmic method next.

gaperez64 commented 8 months ago

One thought about the logarithmic method: for unions we avoid rebuilding trees, but unbalance the ones already there. For intersections though... we still need to rebuild, so this is less promising. I will instead implement the dynamic version. And on that note, the action points are now: