Are there any efficient algorithm for "top hull"?

Question

for example, when points are given in form of (x-left, x-right, y) in x,y coordinate, ( 1 , 5 , 3), (2 , 4, 5) returns (1,2,3) , (2 ,4 ,5), (4,5,3)

Answer 1

The simplest efficient ( O(N log N) ) way to solve this problem is with a "line sweep" algorithm.

Imagine sweeping a vertical line from left to right across the whole set, keeping track of the top-most segment that it crosses. Whenever the top-most segment changes, it is an important event that could affect the top-hull. It would be easy to calculate the top-hull from a list of these changes.

Notice that these important events can only happen at the x positions where one of the input segments starts or ends. Instead of smoothly sweeping the line, therefore, we only need to consider what happens at these x positions. So:

1. Generate a list of all the start and end events for the segments. For a segment { 1, 2, 5}, for example would generate events {1, start 5}, {2, end 5}
2. Create a max heap to keep track of the top-most segment.
3. Sort all the events by x position, and process them in order. For events with the same x position, do the start events first. This ensures that you process each segment's start event before its end event.
4. For each x position in the list, process all the events with that x position as a unit. For each start event {x, start y} add y to the heap. For each event {x, end y}, remove y from the heap.
5. When you're done processing the events for an x position, the biggest element in the heap is the y position of the top-hull until the next x position in the list.