5
$\begingroup$

A well known algorithm in computational geometry is the sweep plane algorithm. I've been trying to find if there's a general version of the sweep plane algorithm in $\mathbb{R}^n$, I don't need to implement it but I need to study how the general version would work.

If there's nothing you known in literature, how difficult is trying to formalize it?

I believe it could be formalized recursively (like sweeping hyper planes from dimension $n-1$ downto $2$. But I need to be sure.

Update:

I've been asked to elaborate a bit more...

In the best reference I know, the plane sweep is basically explained as "Imagine this plane that moves through event points, where something happens". The specific instance are almost 2D and 3D cases (involving problem like segments intersection, triangulation and voronoi diagrams), nothing is mentioned how the paradigm works in general.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "general version"? The sweep line is an algorithmic concept, just like divide & conquer or dynamic programming. The specifics of every instance depend intimiately on the problem at hand. $\endgroup$ – Raphael Nov 10 '16 at 16:41
  • $\begingroup$ Hoping I've clarified a bit more. $\endgroup$ – user8469759 Nov 10 '16 at 16:49
  • 1
    $\begingroup$ Please make sure ever revision of your question is one contiguous post. But no, I don't think that helps. The description you quote is perfectly general; just use a hyper-plane. $\endgroup$ – Raphael Nov 10 '16 at 17:12
  • 2
    $\begingroup$ The sweep line algorithm for line segment intersections does not easily generalize to 3D, as far as I know. Perhaps the question is whether there exists general techniques to construct nD versions of 2D sweep-line algorithms. $\endgroup$ – Discrete lizard Feb 2 '17 at 22:40
  • $\begingroup$ @Discrete lizard, Yes. That's exactly what I was up to. $\endgroup$ – user8469759 Feb 3 '17 at 8:45
1
$\begingroup$

Perhaps this is too broad a question for a coherent answer, so let me first try to say something about line segment intersection, at least. The main reason the sweep-line algorithm is efficient is that we only have to worry about neighboring line segments. We can generalize this procedure to $\mathbb{R}^n$ by noting that if we sweep a line over a sub-plane of $\mathbb{R}^n$ (i.e. the projections of all segments from $\mathbb{R}^n$ on this plane), any intersecting segments in $\mathbb{R}^n$ cannot be 'separated' on this line by a segment that intersects neither of them (If such a segment exists, the segments would be separated by the $n-1$-dimensional hyper-plane orthogonal to the projected plane). So, we can in fact apply the $2D$ algorithm on some plane projection, with the only difference being that we test individual intersections in $\mathbb{R}^n$. (some non-general position edge-cases might get even nastier, but I think the general procedure still applies)

Now, for the sweep line paradigm in general:

I think the main algorithmic idea is that if we want to answer questions about objects in $\mathbb{R}^n$ that concern only their 'neighbor' objects (line segment intersection is the most clear, but Voronoi diagrams and even triangulation fit this description to a certain extent), it is efficient to only query for 'local' objects. To achieve this, sorting seems like a good idea. However, there is no clear method to sort points in $\mathbb{R}^n$ in an useful way, for $n>1$ (I will explain why later*), while sorting in $\mathbb R$ can be efficiently maintained, using binary search trees.

So, the sweep line algorithm attempts to solve this problem by sorting on the order in one direction, on the sweep line. The main thing that the algorithm has to do is to 'make up' for this simplification by traversing the space in a structured matter. Therefore, it makes little sense to use an $n-1$-dimensional hyper-plane to sweep the space with, as we cannot sort the projections on this plane.

Another idea is that the sweep line paradigm allows the algorithm to 'ignore' already visited points. While this is intuitive, I don't think that this idea is the key to efficiency. This idea leads to replacing $n^2$ by $\sum_{i=0}^n i$, so it gives no asymptotic improvements.

So, I think that we have an answer to your statement:

I believe it could be formalized recursively (like sweeping hyper planes from dimension $n−1$ downto $2$. But I need to be sure.

The sweep line paradigm uses a line**, even in $\mathbb{R}^n$.

*: Why can't we just use a lexicographical sort on a 2D-plane and call it a day? Recall why we sort: we want to find 'neighbors' of the objects since we don't need to compare non-neigbors. In $\mathbb{R}^n$, point $p$ being a neighbor of some point $q$ usually means that the (Euclidean) distance between them (in some direction) is minimal, i.e. there is no closer point $r$ 'in between them'. So, our order must be 'distance preserving'. This property is not satisfied by a lexicographical sort.

For example, draw a 4x4 grid of dots, choose to sort by row major or column major order, give them a number to indicate their rank and observe that some neighboring dots differ by 5, more than all other points in the same row/column! We can show that there is no (total) ordering on $\mathbb{R}^n$ that preserves 'neighbors' of points.

However, we must first make this more precise. Observe that an ordering of $\mathbb{R}^n$ is actually a function to some subset of $\mathbb{R}$! (You can also consider it a space-filling curve, the idea is similar) That is, given a total ordering on $\mathbb{R}^n$, there is a function $F : \mathbb{R}^n \rightarrow \mathbb R$ that completely characterizes it (I could make this more precise, but I feel that that's for another question). For a function $F$ (or functional, in this case) to be 'distance preserving', it means that there exists some $c\in \mathbb R$ such that $\|Fx\| = c\|x\|$ for all $x\in \mathbb{R}^n$. If $F$ is non-linear, it is not distance preserving (again, showing this is out of scope).

If $F$ is linear, our condition implies that it is an (linear scaling of an) orthogonal linear map (by definition, depending on your point of view), which means in particular that $F$ is of full rank. This means that $F$ cannot map from a subspace (the plane) to one of strictly lower dimension (a subset of $\mathbb R$). Therefore, there exists no distance preserving $F : \mathbb{R}^n \rightarrow \mathbb R$ and therefore no 'distance preserving' ordering of $\mathbb{R}^n$ for $n>1$ exists. Finally, this means (here I'm making an 'informal leap') that there is no 'neighbor preserving' ordering on planes and hyper-planes.

**The key part of the sweep line paradigm is the projection to a one-dimensional space to be able to use sorting, such as a line. This space does not have to be linear, however. Therefore, we can in some cases (line segment intersection is not such a case) do something similar with not a line, but with a curve (In the setting when our objects are lines, this curve needs to always intersect each line exactly once, so we cannot use a space-filling curve). This is called a topological plane sweep. See the lecture notes by David M. Mount for more information.

$\endgroup$
  • $\begingroup$ I've asked the question ages ago. But anyway by hyper-planes I meant the spaces where the lines are embedded. About the order, I thought that the lexicographic order was fine. However my issue was that there's no general pseudocode for the line segment in $R^n$, at least for my knowledge. I'm not a specialist in computational geometry, I just tend to investigate further each time I come across some related problem. $\endgroup$ – user8469759 Feb 3 '17 at 11:31
  • $\begingroup$ @user8469759 A lexicographical order does not work, unfortunately. I've updated my answer to expand on why an ordering on a higher dimensional object than a line won't help. From the procedure I sketched should be able to implement line segment intersection for $\mathbb{R}^n$, given that you can test whether 2 line segments in $\mathbb{R}^n$ intersect(this is 'just' linear algebra), but do tell if anything is unclear. Furthermore, I can hardly be called an expert in computational geometry (I followed a single half-semester course), but don't hestitate to ask if there's formalism you don't get. $\endgroup$ – Discrete lizard Feb 3 '17 at 17:35
  • $\begingroup$ So, to add to my comment, you should consider creating pseudocode to be 'left as an exercise' ;) $\endgroup$ – Discrete lizard Feb 3 '17 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.