algorithm - How can you find points in regions of space quickly -

algorithm - How can you find points in regions of space quickly -

consider 5 dimensional space has been partitioned @ to the lowest degree 2 planes go through origin. if there n planes number of distinct pyramidal regions creates n^4/24-n^3/4+(23 n^2)/24-(3 n)/4+1 long in "general position", term create specific below.

a hyperplane through origin can defined single vector starting @ origin orthogonal plane. hyperplanes in general position if no 3 of vectors defining hyperplanes coplanar.

how can find 1 point per pyramidal part efficiently in 5 dimensional space? homecoming k points in 5d space, each of in different pyramidal region. value k part of input.

my naive effort far picks points uniformly @ random on surface of hypersphere using (in python)

def points_on_sphere(dim, n, norm=numpy.random.normal): """ http://en.wikipedia.org/wiki/n-sphere#generating_random_points """ normal_deviates = norm(size=(n, dim)) radius = numpy.sqrt((normal_deviates ** 2).sum(axis=0)) points = normal_deviates / radius homecoming points

and chooses subset each 1 in different region. can verify points in different pyramidal regions using next code.

def all_in_distinct_pyramidal_regions(testpoints, hyperplanes): signs = numpy.sign(numpy.inner(testpoints, hyperplanes)) homecoming (len(set(map(tuple,signs)))==len(signs))

here image of 4 planes in 3d 14 points, 1 in each part (because 5d hard draw), 1 in each of pyramidal regions created planes.

is there algorithm works in 5 dimensional space find k points, each in different pyramidal regions , takes o(nk) time?

i have noticed pyramidal regions convex. convex spaces closed under add-on , in particular seems if knew hyperplanes formed border of part potentially find point within part averaging points on hyperplanes. however, not sure how turn observation total efficient algorithm.

if you're willing dig python library linear programming, here's approach that's easy implement , reasonably efficient (time o(poly(n) k)). it's similar 1 gene proposed.

let v1, ..., vm in r^5 \ 0 normal vectors of planes. find point in intersection of positive halfspaces, solve linear program

maximize z subject v1 . x - z >= 0 ... vm . x - z >= 0 x in [-1, 1]^5 z in r,

in variables x, z, . denotes dot product. if z > 0 in optimal solution, point x in intersection of positive halfspaces.

to find 1 point in each region, enumerate recursively vectors of length n containing entries ±1, next pruning. interpret entries of vector choosing positive or negative halfspace of each normal vector. if lp subset of constraints corresponding current prefix infeasible, prune recursion. in pythonish pseudocode:

def find_points(normals, prefix=()): "solve lp normals [sign * normals[i] i, sign in enumerate(prefix)]" if "the lp infeasible": pass elif len(normals) == len(prefix): yield x else: point in find_points(normals, prefix + (1,)): # or yield yield point point in find_points(normals, prefix + (-1,)): yield point

thanks pruning, number of internal nodes of recursion tree @ n times number of regions, not @ exponential.

the bottleneck of approach solving linear programs. since add together constraints 1 @ time, if lp solver supports it, specify dual simplex algorithm , reuse previous dual solution starting basis.

algorithm math