My question is n-dimensional, but I will begin by dropping the problem down to two dimensions for clarity's sake. It regards defining what is a solution by defining one or more data points that are known to be solutions and a set of linear bounds.Lets say you have a two-dimensional grid of discrete units that exists within a limited domain, say 1000 x 1000. I'll refer to that domain as D, and reference units within that domain via zero relative c-style array operators (e.g. D[0][0] and D[999][999]).We also have a function L describing a line segment defined by two points in 2 and within the bounds of D. D[5,5] and D[10.4, 2.6] would be valid points, whereas D[1020, 40] and D[503, 2000.7] would not.We then create some random set of line segments S{L1, L2,...,Ln} that may or may not intersect with other line segments in the set and define some point P in 2, like (5, 6.7), that is bounded by D and does not intersect with any line segment in S.If we imagine P as a water source, and S as a set of barriers, the water would spread out and fill some solution area that could be bounded by a set of lines B such that each line connects to the beginning of the next in a loop. Each line is infinitely thin, so lines that project into the water could have the option of not influencing the solution region:You would then use the point to define the solution area, and determine the set of units in D that are part of that solution area.If you take this scenario to three-dimensions, you could imagine water filling a volume in a similar manner, generating a three-dimensional bounds object. This can then expand to four or more dimensions.I suspect the problem would become easier if I split line segments into two line segments at the points of intersection.I've looked at some isosurface algorithms and modified dilation (fill) algorithms for solving this problem, but they seem very inefficient, especially given extremely large domains, or domains whose resolution relative to the set of bounds functions can be arbitrarily set. The problem grows when the domain has more than three dimensions.I'm certain that this sort of problem has been dealt with before, as restricting the domain of large data sets down to a solution set using a set of bounds in a time-efficient manner is fundamental to many big-data problems. I'm mainly looking for resources and algorithms related to this problem that I might be able to use?EDITThe solution set can also have holes. For example, a bounds with the appearance of a square inside a square, with the solution point between them, would produce a solution area that looked like a square with a square hole in it.EditThe more I think about it, the more I think this might actually be a graph-theory question.
Finding a cell in an arrangement of simplices
computational geometry;convex geometry;arrangements
If I am understanding your problem correctly, this is the problem of computing the face containing a given point in an arrangement of line segments. There is a randomized algorithm running in expected time $O(n\alpha(n)\log n)$, where $n$ is the number of line segments, and $\alpha(n)$ is the inverse Ackermann function. The algorithm computes the boundary of the face, and from that you can list the grid points if you want using a sweep algorithm, but the time to do that will of course depend on the number of grid points inside the face.