Consider the following problem: we are given a finite set of bounded line-segments in ${\mathbb R}^3$, and we want to decide whether there exists a point $p\in {\mathbb R}^3$ from which no two segments obscure one another.

Can this be done efficiently?

Problem statement:

More precisely and formally: we are given $n$ line segments $\ell_1,\ldots,\ell_n$, where each segment is defined as $\ell_i=\{tu_i+(1-t) v_i: t\in [0,1]\}$ with $u_i,v_i\in {\mathbb Q}^3$ (we assume rational coordinates).

We wish to decide whether there exists a point $p\in {\mathbb R}^3$ such the lines connecting $p$ with each point on the lines are distinct, and if so, compute it.

Is there an efficient solution? Is there a hardness lower bound?

UPDATE: Given the lack of answers so far, what about the case where the line segments connect two adjacent point in a 3D $k\times k\times k$ grid ? Then, they are all parallel to some axis, they are all of length 1, etc. Does this make it significantly easier?

Inefficient solution:

Observe that for each pair of lines $\ell_1,\ell_2$, the points from which the lines do obscure each other can be described as a polyhedron defined as the intersection of 4 half-spaces: for every 3 points in {u_1,v_1,u_2,v_2}, the hyperplane defined by them is a boundary such that on one side of it, the lines do not obscure each other.

Thus, we can represent the set of "bad points" (those from which at least one pair obscure each other) as a union of $n^2$ polyhedra (not necessarily disjoint). Then, all we need is to test it's complement for emptiness. This can be done e.g. using Fourier-Motzkin quantifier elimination, whose complexity is quite bad. On top of this, we first need to convert a CNF representation to DNF, which may involve an exponential blowup.


Your Answer

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

Browse other questions tagged or ask your own question.