I was given a array R of n rectangles [each element in the array is a bottom left point(x1,y1) and a top right point (x2,y2)] , parallel to the axis, and an array P of n points [each element is a point (x.y)].

I need to write an algorithm that finds a point in the P array that appears in the largest amount of rectangles from the R array. Complexity required is O(n*logn) I know about the concept of point of maximum overlap but this refers only to the x-axis i.e. http://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/

How do I find a point of maximum overlap that fits both axis?

I thought about using a sweeping line, but I don't know how it fits the required complexity.

any ideas?


  • 2
    $\begingroup$ Welcome to CS.SE. I suggest you spend some more time on this problem. It sounds like you have thought about using a sweep line algorithm; think about it some more. Don't worry yet about its complexity. Just try to think -- how could you use a sweepline algorithm? What techniques do you know? Try identify a specific sweepline algorithms (what will the steps be? can you write them down?); then try to analyze its running time. If you get stuck, edit the question to show your progress so far, the approach you are thinking of, and where you're stuck. For now, keep trying and don't give up! $\endgroup$
    – D.W.
    Jun 15, 2017 at 16:46
  • $\begingroup$ Thank you but your comment is way too general and hasn't helped me that much. You literally said things that are very obvious and non-progressive in any way. Please be more specific if you want to help because I've spent hours on this with no progress. $\endgroup$
    – Jamaico
    Jun 16, 2017 at 22:39
  • $\begingroup$ It's hard to know how to give you specific comments: the only thing you've told us is that you thought about using a sweep line algorithm but couldn't succeed. Without telling us anything about what kinds of ways you tried to apply those methods, and without knowing you personally and knowing how well you understand sweep line methods, it's hard to give you specific, personalized feedback. I suggest reviewing other sweep line algorithms, then editing the question to explain why you found it hard to adapt them here. $\endgroup$
    – D.W.
    Jun 16, 2017 at 23:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.