Segment Overlaps

Now, we assume that there are overlaps among segments of the same slope. Algorithm 2 still works, but it is not output sensitive anymore. Suppose the first subset S₁ has two horizon-tal segments ℓp and ℓq which overlap each other. Then, if we apply Algorithm 2, it reports the intersecting pair (ℓp, ℓq) in the first stage. Then, in the second stage it examines pairs (S₁,S₂),(S₁,S₃), . . . ,(S₁,S_m) to perform the plane sweep. For each pair the intersection (ℓp, ℓq) is detected. Thus, we have to know how to avoid such an intersection due to overlap in the sec-ond stage.

Now we have three problems:

Isothetic Segment Intersection Reporting: Given a set of isothetic segments, report all inter-sections of those of different directions.

Horizontal Segment Overlap Reporting: Given a set S of horizontal segments and a query horizontal segmentℓq, report all segments inS which overlapℓq.

Vertical Segment Overlap Reporting: Given a setS of vertical segments and a query vertical segmentℓq, report all segments inS which overlapℓq.

Since the last two problems are just symmetric, we just consider Horizontal Segment Over-lap Reporting Problem. Once we report all overOver-laps, we just apply our previous algorithms to report all intersections of isothetic segments.

Horizontal Segment Overlap Reporting

We are given a setS ofnisothetic segments. We have seen two different ways of decomposing S into subsets of size O(s), one by indices and the other by slopes. In either way we have O(s) horizontal segments and we want to report all overlaps with them. For that purpose we first build a binary search tree using theiry-coordinates as keys. Then, two or more horizontal segments may have the same y-coordinate. We create just one leaf node for those segments sharing the same y-coordinate. We apply the Chazelle’s filtering search technique to those segments [25]. Since all those horizontal segments have the same y-coordinate, they can be regarded as intervals. Thus, given a query interval, we can report all k intervals in the data structure intersecting the query one inO(k+logs) time.

Theorem 24 Given n segments without any overlap in the plane stored in a read-only array and a parameter value s between O(1)and O(n), Algorithm 5 correctly reports all Kh overlaps between input horizontal segments in O((n²/s) logs+K_h)time using O(s)words.

Proof. Each subsetS_i contains at mostshorizontal segments. We can build the binary search tree inO(slogs) time. Then, for each leaf node containing more than one segment we reform them for filtering search. It is done in in linear time using linear space (since all the segment endpoints can be sorted in the preprocessing step). Then, we can report allK_hiinterval overlaps in an output sensitive way using the filtering search. Hence, the total running time is given by

∑ each S_i

O(slogs+K_hi+nlogs)=O(K_h+(n²/s) logs).

2 Algorithm 5: Horizontal Segment Overlap Reporting for a set of horizontal segments using the filtering search.

Input: A setS ofnhorizontal or vertical line segments in the plane stored in a read-only array and a parameter values.

Output: All K_h overlaps among the input horizontal line segments.

/* Preprocessing stage: */

Partition the setS intom=n/sdisjoint subsetsS₁,S₂, . . . ,S_musing Index Partition.

1

foreach subset S_i do

2

LetH(S_i) be a set of all horizontal segments inS_i.

3

Build a binary search tree usingy-coordinates of those horizontal segments.

4

At each leaf node containing more than one segment, build the data structure for

5

filtering search. foreach horizontal segmentℓqin S_i ∪ · · · ∪S_mdo

Report all overlaps ofℓqwithH(S_i) except (ℓq, ℓq) using the data structure.

6

end

7

end

8

Symbolic Perturbation

Once we have reported all overlaps among segments of the same slope (horizontal or vertical), we report all intersections between horizontal and vertical segments. What is required here is to avoid reporting segment overlaps among those of the same slope.

It is easy. For example, Algorithm 2 can be adapted as follows. In the first stage we do not need to report segment overlaps. For the purpose we vertically shift each horizontal segment, say ℓp, by pδ for a positive small constant δ. For each vertical segment, we extend it upper endpoint upward by nδ. If the constant δ is small enough, this extension causes no problem.

More exactly, this modification does not create any new intersection. After the modification we perform a standard plane sweep.

In the plane sweep algorithm we have three different types of events caused by left and right endpoints of horizontal segments and vertical segments. At a left endpoint of a horizontal segment, say ℓp, we insert ℓp into a data structure called a y-list which keeps all horizontal segments intersecting the current vertical sweep line in the sorted order. We order them by the lexicographical order using theiry-coordinates and indices. That is, when two horizontal segmentsℓpandℓqoverlap each other andp<q, we decideℓp< ℓq. Or, more formally, for two horizontal segmentsℓpandℓq, ℓp < ℓq holds if they-coordinate ofℓp is smaller than that ofℓq

or they are equal and p< q. This is equivalent to shifting each horizontal segmentℓpvertically by pδfor a small positive constantδ >0.

At a right endpoint of a horizontal segment, sayℓq, we just deleteℓqfrom they-list. When the sweep line comes to a vertical segment, sayℓr, we locate its two endpoints in they-list. For the lower endpoint, we use itsy-coordinate so that it becomes below any horizontal segment of the samey-coordinate if any. For the upper endpoint, we use itsy-coordinate plus nδso that it lies above any horizontal line of the samey-coordinate if any. Once we locate the two endpoints in they-list, we can report allk_rintersections onℓrinO(k_r+logs) time.

In practice we do not use the constant δ. The same operations are done in a symbolic manner. This simple symbolic perturbation is effective to avoid duplicate report of overlapping segments. The time complexity of the resulting algorithm is just the same as before.

An example is given in Figure 5.3. There are 12 horizontal segments ℓ1, . . . , ℓ12 and two vertical segmentℓ13 andℓ14. Among them the three segmentsℓ5, ℓ8, ℓ10 and two endpoints (the upper endpoint of ℓ13 and the lower endpoint of ℓ14) have the samey-coordinate in the figure.

After the modification stated above, the three horizontal lines are vertically shifted by their indices. The upper endpoint ofℓ13 lies above all of them and the lower endpoint ofℓ14 below them.

ℓ₁ ℓ2

ℓ₃

ℓ₄ ℓ5

ℓ6

ℓ7

ℓ8

ℓ₉ ℓ10

ℓ12

12 22 30 32 38 55 64 72 ℓ₁₄

ℓ₁₃

Figure 5.3: A set of horizontal segments with overlap. Three segmentℓ10, ℓ8, ℓ5have the same y-coordinate 55, but they are slightly shifted in the figure.