Solution:

The brute force approach would be to store the starting and the ending co-ordinates for each line segment in an array A and then for the current segment, check if it intersects or "touches" any one of the previous line segments present in the array A. The run-time and space complexity of this approach is O(N^{2}) where N is the number of line segments. Can we do this in a run-time complexity of O(N) and space complexity of O(N) with O(1) extra space ?

BTW since we are only provided with the lengths of line segments, we can easily convert these lengths into (X, Y) co-ordinates.

The important observations we make here are:

- The current line segment X
_{i}can only intersect (or touch) with line segments numbered X_{i-3}, X_{i-4}, X_{i-5},... and so on. - Due to the cyclic property of the line segments, if the line segment X
_{i}intersects another line segment X_{j}where j < i-5, then X_{i}also intersects the line segments X_{i-5} - The last property ensures that we need to scan for possible intersections only for X
_{i-3}, X_{i-4}and X_{i-5}

The second property can be proved by observing that X_{i} and X_{i-6} are along the same axis but move towards opposite direction, thus X_{i} can only touch the near end of X_{i-6}. But the near end of X_{i-6} also touches X_{i-5}, thus X_{i} also touches X_{i-5}.

X_{i} and X_{i-7} are along orthogonal axis, thus X_{i} can either intersect X_{i-7} or can touch one of its end. But X_{i-7} and X_{i-5} are both along the same axis and also X_{i-5} lies in between X_{i} and X_{i-7}, thus X_{i} cannot intersect X_{i-7} without intersecting X_{i-5} first.

By induction we can prove that if X_{i} intersects or touches any X_{i-k} for k < 7, then it also intersects or touches X_{i-5}. For e.g. if k is even then it touches X_{i-k+1} and if k is odd it intersects X_{i-k+2}. Now apply induction on X_{i-k+1} and X_{i-k+2}.

Interestingly we can determine whether any path crosses or not without converting the line segments to co-ordinates as used in the following very short Python code:

class Solution(object): def isSelfCrossing(self, x): if len(x) < 4: return False for i in range(3, len(x)): a = x[i] >= x[i-2] and x[i-1] <= x[i-3] b = i >= 4 and x[i] + x[i-4] >= x[i-2] and x[i-2] > x[i-4] and x[i-1] == x[i-3] c = i >= 5 and x[i] + x[i-4] >= x[i-2] and x[i-2] > x[i-4] and x[i-1] + x[i-5] >= x[i-3] and x[i-3] > x[i-5] and x[i-1] <= x[i-3] if a or b or c: return True return False

The boolean variables 'a', 'b' and 'c' track whether X_{i} crosses X_{i-3}, X_{i-4} and X_{i-5} respectively.

Categories: PROBLEM SOLVING

Tags: Computational Geometry, Constant Space, Leetcode, Line segment, Self Crossing

### Leave a Reply

You must be logged in to post a comment.