<p>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 <a href="http://epubs.siam.org/doi/pdf/10.1137/0222077" rel="nofollow">randomized algorithm</a> 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.</p>

CC BY-SA 3.0
2016-10-29T21:20:06.690Z
It looks like a three-dimensional version is accomplished to a certain extent within the openVDB library.
AaronF
CC BY-SA 3.0
2016-10-20T21:28:13.480Z
2016-10-20T22:18:48.923Z
2016-10-20T22:18:48.923Z
Sasho Nikolov
<p>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.</p>
<p>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]).</p>
<p>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.</p>
<p>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.</p>
<p>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:</p>
<p><a href="https://i.sstatic.net/ewkQk.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ewkQk.png" alt="enter image description here" /></a></p>
<p>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.</p>
<p>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.</p>
<p>I suspect the problem would become easier if I split line segments into two line segments at the points of intersection.</p>
<p>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.</p>
<p>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?</p>
<p><strong>EDIT</strong></p>
<p>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.</p>
<p><strong>Edit</strong></p>
<p>The more I think about it, the more I think this might actually be a graph-theory question.</p>

CC BY-SA 3.0
2016-10-20T22:17:42.030Z
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
CC BY-SA 3.0
2016-10-21T02:03:09.027Z
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
CC BY-SA 3.0
2016-10-21T13:54:00.727Z
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
CC BY-SA 3.0
2016-10-21T13:58:09.810Z
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
CC BY-SA 3.0
2016-10-22T02:17:27.127Z
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
<computational-geometry><convex-geometry><arrangements>
Finding a cell in an arrangement of simplices
AaronF
# Finding a cell in an arrangement of simplices

(Asked by: username_0 on 2016-10-20)

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:

[![enter image description here](https://i.sstatic.net/ewkQk.png)](https://i.sstatic.net/ewkQk.png)

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.

**Tags:** computational-geometry, convex-geometry, arrangements

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2016-10-20. Score: 2 | Accepted answer

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](http://epubs.siam.org/doi/pdf/10.1137/0222077) 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.

> **Comments:**
> **username_0**: It looks like a three-dimensional version is accomplished to a certain extent within the openVDB library.  

---

