Computational Geometry

Assignment

Ritajit Majumdar
Roll: 91/CSE/111006
June 18, 2014

Contents
1 Problem 2

2 Problem 1
2.1 Part a . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Part b . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Part c . . . . . . . . . . . . . . . . . . . . . . . .

4
4
5
6

3 Problem 3

4 Problem 4

5 Problem 5

10

Problem 2

Let S be a set of n disjoint line segments in the plane, and let p be a point
not on any of the line segments of S. Determine all line segments of S that
p can see, that is, all line segments of S that contain some point q so that the
open segment pq doesnt intersect any line segment of S. Give an O(nlogn)
time algorithm for this problem that uses a rotating half-line with its endpoint
at p.

Solution
Input: Set S = {S1 , S2 , . . . , Sn } of n disjoint straight lines, a point P .
Output: All line segments Si seen from P .
Consider a set N = {Si1 ,Si2 } 0 < i n where Si1 is the start point and
Si2 is the end point of the line segment Si . Let us define event point as the
start and end points of the straight lines. So for n straight lines, there will
be 2n event points. I shall explain the upper half in the algorithm, the lower
half will follow similarly.
Algorithm:
1. Draw a horizontal line passing through P . Let the y-value of this line
be yp .
2. Rotate the half-line counter clock wise in upward direction, stopping
only at the event points.
3. Store the event points as they arrive in a queue. Any data structure will
be suitable where the first event point will be processed first. Queue
seemed most appropriate.
1

4. Now, arrive at each event point popping them from the queue.
5. Stop the half line at the first event point. Include the straight line as
the one seen.
6. Stop at the next point as they are popped. If it is the point of the same
straight line already entered as seen, then proceed without any action.
Otherwise, check the y-value with the y-value of the previous point. If
the y-value is less than the previous one, mark the straight line as seen.
Otherwise, store the straight line.
N.B. This will work because no lines intersect. y-value more means the
straight line is above the current one and cant be seen, at least till
now.
7. Check for the stored stright line. Suppose we reach the end point of
one straight line without entering any other line. Now if the next event
point belongs to the stored straight line, mark it as seen. Otherwise, if
the x-value of the next starting point is less than the end point of the
stored line, then also mark it as seen.
N.B. This is because, since there is no overlapping of lines, there is a
gap between two lines. So the stored line will be visible from that gap.
A condition has been shown in the diagram.
8. Continue this process for all points above the half-line.
9. For the lines below the half-line, start from right and continue clock
wise downward.

The time complexity of this algorithm The inital sorting takes O(nlogn) time.
Now for each line, there are 2 event points. So for n straight lines, there will
be 2n event points, leading to a complexity of O(n).
So the final time complexity is - O(nlogn) + O(n) = O(nlogn).

2
2.1

Problem 1
Part a

You are given a convex polygon P in the plane having nP sides and an xmonotone polygonal chain Q having nQ sides. Give a bound on the maximum
number of intersections that might occur between the edges of P and Q?

Solution
In the following figure, I have taken nP = 7 and nQ = 8.

It can be noted that since P is a convex polygon and Q is a x-monotone

chain, every edge of Q can intersect at most 2 edges of P. A vertex q is said
to be to the right of another vertex p if qx > px or if qx = px and qy > py .
Here qx and qy refers to the x and y coordinate of q respectively.
Thus, a side of Q can at most intersect one of the upper edges of P and one
of the lower edges of P. There can be no edges in between since the polygon
is convex.
4

So an x-monotone chain having nQ number of edges will intersect a convex

polygon atmost at 2nQ number of points.

2.2

Part b

Given P and Q, two x-monotone polygonal chains, give a bound on the

maximum number of intersections that might occur between the edges of P
and Q?

Solution

If P and Q has np and nq vertices respectively, then their respective number of edges will be np + 1 and nq + 1.
Now, between two intersection points, there will be atleast one vertex of
either P and Q. But this vertex is not the first or last vertex of the chain
since on both sides of it, there are intersections. So maximum number of
such points is
5

(np + 1) 2 + (nq + 1) 2 = np + nq 2
Thus after the first intersecting point, there may be atmost np + nq 2
intersecting points. So maximum number of intersections is (np +nq 2)+1 =
np + nq 1

2.3

Part c

Given P and Q, two monotone polygonal chains with different directons, give
a bound on the maximum number of intersections that might occur between
the edges of P and Q.

Solution
Consider the following situation

So the maximum number of intersections is possible when each edge of one

intersects every edge of the other, which gives np nq maximum intersections.

Problem 3

You are given a set of n vertical line segments in the plane. Present an
efficient algorithm to determine whether there exists a line that intersects all
of these segments. (Hint: O(n) time is possible.) Justify your algorithms
correctness and derive its running time.

Solution
Input: A set S of n vertical lines. S ={S1 , S2 , , Sn }
Output: A straight line l that intersects all the n lines, if one exists.
It should be noted that the straight line cannot be vertical, then it will
not intersect vertical lines. So we can take the equation of the straight line
to be y = mx + c. If the line is horizontal, then we will have c = 0 and a
definite value of mx, giving the equation y = const.
Moreover, each straight line in set S is denoted by two pairs of points,
one start point and one end point, i.e. the ith straight line will be trated as
(xi , yi1 ) and (xi , yi2 ).

Algorithm:
7

1. Consider the equation of the required straight line l as y = mx + c.

2. For i 1 to n do
3.

Find the x-value of the equation of the straight line from set S.

4.

Put the x-value in the equation of line l and find the corresponding
y-value.

5.

The y-value may be within the line segment from set s. In that
case there is an equality, otherwise inequality (y-value is greater or less
than the maximum and minimum y-values of straight line respectively)
accordingly.

6. For n straight lines, there will be n inequalities (or maybe equalities in

some case).
7. Use Linear Programming (LPP) to solve all the n inequalities. The
result will be any value chosen from the common region. If no common
region exists, then such a straight line does not exist that intersect all
n lines.
For every one of the n-lines, we need to compute once. The only computation for each line is finding the y-value of l from the x-value of the
line. So for n lines, the time complexity is O(n). Moreover, solving LPP for
n inequalities can be done in O(n) time. So the total time complexity is O(n).
Finally, since LPP always provides the correct region of intersection, the
algorithm in correct. We can choose any y and x value fro the intersecting
line l fromt that common region. This approach will also point out whether
such a line exists. No region of intersection for all n lines means such line
does not exist.

Problem 4

A simple polygon P is star-shaped if there is a point q in the interior of P

such that for each point p on the boundary of P, the open line segment qp lies
entirely within the interior of P. Suppose that P is given as a counterclockwise
sequence of its vertices v1, v2, . . . , vn. Show that it is possible to determine
whether P is star-shaped in O(n) time (Note: You are not given the point
q.). Prove the correctness of your algorithm.

Solution

For every edge ei , draw the corresponding half plane hi whose boundary
lies on the line ei . So for n edges, there will be n half planes h1 , h2 , . . . , hn .
Define H = h1 h2 . . . hn .
If H is not null, then it can be claimed that the polygon is start shaped.
This is because if H is not null, then we can choose a point q H such that

it can see every edge. Thus the polygon is start-shaped, otherwise it is not.
Equation of the lines representing the edges can be found in linear time.
Moreover, once the half-planes are constructed, the problem of finding whether
H is null is a problem of linear programming which may be solved in linear
time.
So total time complexity is O(n).

10

Problem 5

The code for the problem has been attached with the mail. A test case and
the corresponding output is also given along with it.

11