Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Given is a finite set $S$ of line segments in the plane.
I am interested in finding a line $l$ which splits some segments in $S$ into two, thus yielding a new set of line segments $S'$.
Here splitting means that if $l$ intersects a line segment $xy$ in a point $z$ then $xy$ gets replaced by two new line segments $xz$ and $zy$.


The goal is to chose $l$ such that it minimizes the length of the longest line segment in $S'$.

I would be interested to know if this problem has been studied before. What confuses me is that the problem does seem to be continuous and not discrete.

share|improve this question
1  
Suppose you knew the optimal length $\ell$. Then on any line of length $L \ge 2\ell$, there's an interval (centered at the midpoint) that the optimal line must pass through. Now you have the problem of determining whether a single line can simultaneously pass through a collection of line segments, which can be solved using the dual space (is there a point in the intersection of a collection of double wedges). –  Suresh Venkat Feb 1 '13 at 8:02
add comment

1 Answer

up vote 4 down vote accepted

I don't know about whether this specific problem has been studied before but I can point you to a general class of problems that include it and that have been studied: This looks like an LP-type problem (or perhaps even a low-dimensional linear program although I am not quite seeing how to coordinatize it so that works). If so it can be solved by a linear-time combinatorial algorithm.

To set this up as an LP-type problem, we need an objective function mapping sets of line segments to some totally ordered set of solution values. The obvious objective function to use here is the numerical value $l$ that you're trying to optimize (the length of the longest split segment), but I think that's not quite good enough. Instead you should use a lexicographic combination of $l$ with the coordinate vector of a line achieving value $l$. With this lexicographic combination, the problem automatically satisfies the monotonicity and locality properties of LP-type problems: adding another segment to an instance only makes its solution worse, and if a given line is the solution to two sets $A\subset B$ of segments, and adding a new segment $x$ to $A$ doesn't change the solution (because the line cuts $x$ in pieces shorter than $l$) then adding $x$ to $B$ also doesn't change the solution (because the same line cuts $x$ in the same way).

So the main remaining question is whether this problem has bounded dimension, where the dimension of an LP-type problem is defined as the largest size of a minimal instance with a given solution value. So, in any problem of this type, is there a subset of a constant number of the line segments that has the same solution as the whole problem? I think the answer must be yes, because the optimal line must cross some three segments at points that are at distance $l$ from the ends of their segments (else it could be moved continuously to a better solution) and those three segments should determine the solution value.

share|improve this answer
    
This is very helpful to me since I didn't know about LP-type problems before. Thank you very much. –  101011 Feb 1 '13 at 20:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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