'Given non-crossing n rectangles and n triangles find a segment crossing all 2n rectangles and triangles

Given n rectangles and n triangles find I am trying to think of a algorithm to find a segment crossing all 2n rectangles and triangles.

My idea:

  1. Find the convex hull of all the given points.
  2. Find the two farthest point on the convex hull, Lets say p and q.
  3. Let P and Q be the shapes p and q belong to, respectively.
  4. For every point in P, draw a line to all Q points.
  5. Check if any of these lines cross all the 2n shapes.

total complexity is O(nlogn).

I know for sure a more efficient solution doesn't exist, but im not sure if this solution works (so far i was not able to find a counter example, but was not able to proof the correctness of my algorithm).

I need some help on finding a working algorithm for the problem. Will my algorithm do the job?

any help will be appreciated.

algorithmcomputational-geometry


Solution 1:[1]

Counterexample:

+---+                         +---+
|   |                         |   |
|   |                       __|   |
|   |                       \/|   |
|   |                         |   |
|   |                         |   |
+---+                         +---+

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Matt Timmermans

Related Questions