# Finding a cell in an arrangement of simplices

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?

EDIT

The 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.

Edit

The more I think about it, the more I think this might actually be a graph-theory question.

• BTW it's not clear how you want to generalize this to higher dimensions. What plays the role of the segments in three dimensions? Triangles? Any two-dimensional polygon? Something else? – Sasho Nikolov Oct 20 '16 at 22:17
• A two dimensional planar segment in three dimentions plays the roll of a one dimensional linear segment in two dimensions. This would probably be a triangle. – AaronF Oct 21 '16 at 2:03
• I don't think "three dimensional planar segment" has meaning in any standard terminology. As a segment is a one-dimensional simplex, I am guessing you want a $d$-dimensional simplex when working in $d+1$ dimensional space. So, a triangle in 3d. – Sasho Nikolov Oct 21 '16 at 13:54
• If you don't mind, I would change the title of your question to "finding a cell in an arrangement of simplices." That would sound much more familiar to theorists than "isosurface bounds in a voxel field". Also it describes your problem more accurately. I am afraid your current title is scaring people away. – Sasho Nikolov Oct 21 '16 at 13:58
• Yeah, I think you're right. The main point is, that the bounds can contain the solution set in whatever dimension you're dealing with. A bound would be in the same vector space as the domain, but have one less dimension. – AaronF Oct 22 '16 at 2:17

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.