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

Add truncated Voronoi cells #160

Open
lcgraham opened this issue Mar 21, 2016 · 3 comments
Open

Add truncated Voronoi cells #160

lcgraham opened this issue Mar 21, 2016 · 3 comments

Comments

@lcgraham
Copy link
Contributor

Update certain Voronoi approximations to provide a cut-off distance (or directed distances) in a particular metric (thus defining a "cover" of any Voronoi cell by a simpler box defined by distance(s) and metrics). This can be used to speed up nearest neighbor searches since comparisons would not even need to be made with respect to samples that are farther away than the cut-off distances. It is very much like creating a pre-processing "filter" that is much like an indicator/characteristic function of the covering sets. This is particularly useful for emulation.

@eecsu
Copy link
Contributor

eecsu commented Mar 21, 2016

Using gradients to define the scaled boundary box by
$$ (x - g)^\top diag(\abs{\nabla q}) (x-g) \leq \text{bd. tol.} $$

@lcgraham
Copy link
Contributor Author

This truncated_voronoi_sample_set should be a subclass of voronoi_sample_set (see #178) with the additional attributes self._radii and self._normalized_radii whereself. _normalized_radii is the radii of the Voronoi cell when self._domain is normalized to the unit ball. If gradients are present these should be able to be set with self.set_normalized_radii() and self.set_radii(). Query will need to be updated to include distance_upper_bound as follows: self._kdtree.query(x, p=self.p_norm, distance_upper_bound=self._radii)

@lcgraham
Copy link
Contributor Author

Note that these are not centroidal Voronoi tesselations meaning that the centroid is NOT the generator of the Voronoi cell. What we desire for the radius is actually :math:sup_{\lambda \in \mathcal{V}_{i, N}} d_v(\lambda, \lambda^{(i)})

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants