CODEWITHSUNDEEP
algorithmdata-structures
PassionateCoder
PassionateCoder

Reputation: 27

How do I solve this Algorithms question . What can be the optimal time and space complexity?

You have 𝑁 rectangular papers on a desk, and you want to pin them down with a pin. Given positions, sizes and orientations of papers, design an algorithm that determines whether they can be pinned with only one pin or not. Note that, you cannot move or rotate papers.

Edit:

I thought of first decomposing each rectangular papers into small triangles (Using Triangulation Decomposition Law) and then find that area of small grids which are common to all the rectangular papers. And then pin the common area

Upvotes: 1

Views: 128

Answers (3)

Doug Currie
Doug Currie

Reputation: 41180

This is the same algorithm that's used in graphics programming to do "clipping." Starting with the first sheet of paper, clip the remaining overlap polygon with the next rectangular sheet. All the resulting polygons will be convex, so a 2D convex polygon clipping algorithm can be used. This one lists the steps for performing the intersection as:

1. Create an empty polygon as P
2. Add all corners of Polygon1 that is inside Polygon2 to P
3. Add all corners of Polygon2 that is inside Polygon1 to P
4. Add all intersection points to P

If at any point you have no intersection, then there is no place to put the pin.

See this SO Q&A for more ideas.

Upvotes: 2

Codor
Codor

Reputation: 17605

If arbitrary rotation is permitted, the problem can be modelled by using linear programming. The dimension of the problem is 2 (as the pieces of paper lie in the plane) and 4 constraints per rectangular piece of paper are needed to describe its shape. The rectangular pieces of paper can be fixed using a single pin if and only if the intersection of all of the rectangular pieces is nonempty. In total, the problem can be solved within a polynomial runtime bound using the ellipsoid algorithm (however this is more a theoretical result).

Upvotes: 0

tucuxi
tucuxi

Reputation: 17945

This is not a full answer, but should help you find one.

  1. Two papers that do not overlap cannot be pinned together. Only if all papers overlap with each other is an answer of "true" possible, but even then, it is not guaranteed: imagine a triangle built of rectangles that overlap pairwise. No single pin would hold it together.

  2. Two rectangles overlap only if either one fully contains the other, or if their edges cross each other somewhere. If a vertex from one rectangle is inside the other, they overlap. If an edge from one rectangle crosses an edge from another, they overlap. In all other cases (no vertex contained, and no edge crossings), they do not overlap.

  3. Given two rectangles that overlap, any pin that must hold all rectangles together must pass through the overlapping area. You can discard the rectangles and simply continue using the overlapping area (which will generally not be rectangular) in their place. All these observations apply equally to rectangles and general polygons.

Upvotes: 0

Related Questions