1. All codes should be written in C/C++ that can be compiled using GNUcompiler and run in Ubuntu.
2. Dont copy codes from other groups. It is subject to penalty or failing in theextreme case.
3. All group members should participate in coding and with uniform division oftasks. In vivas, we may ask each individual to modify codes so as to change something or the other.
4. How to write an svg file?

Just download and save http://cse.iitkgp.ac.in/~pb/test.svg. Open it in a browser, and also open it a plain text editor. Compare the image with the textyou will understand the basics. Its very simple.

There are many resources on svg file format available in Internet. The most important one is http://www.w3schools.com/svg/ where you will find many examples.

A properly written svg can always be opened and seen in any browser like Mozilla or Chrome, and also in any standard image viewer. So, just check and ensure that the output svg produced by your code is opened and seen properly in these two browsers.

5. Use proper indentation and commenting in your codes so that we can understand your code.
6. Write in the beginning of each code the following:
   1. your names and roll nos.
   2. purpose of the code / problem description in briefiii) compilation and execution instructions in Ubuntu iv) any other point that you feel important.
7. You have to submit all source codes and 3 sets of input and output files (small,medium, and large sizes).

1 Convex hull (divide and conquer)

20. Write a program to randomly generate n distinct points such that their coordinates are integers in the range [20,800] and divisible by 20. User input: n.

Store the value of n and the coordinates of all n points in a plain text file named points.txt.

1. Write another program that reads the file txt and constructs its convex hull using divide and conquer.

Visualize the left convex hull in red and the right one in blue.

For the left convex hull, find the convex hulls of the points lying in its interior, and visualize them as above.

For the right one, do similar.

So, finally, hierarchical convex hulls will be formed.

Save the final result as an svg file named hull.svg in which all n points are colored black and hull edges colored red / blue.

2 Convex hull (Graham scan)

20. Write a program to randomly generate n distinct points such that their coordinates are integers in the range [20,800] and divisible by 20. User input: n.

Store the value of n and the coordinates of all n points in a plain text file named points.txt.

1. Write another program that reads the file txt and constructs its convex hull using Graham scan. Visualize the convex hull H₁ in red.

Next, find the convex hull H₂ of the points lying in the interior of H₁, and visualize it in blue.

This way, hierarchical convex hulls will be formed.

Save the final result as an svg file named hull.svg in which all n points are colored black and hulls are colored alternately in red and blue.

3 Euclidean MST by Prims Algorithm

The task is to find MST by Prims Algorithm for a completely connected Euclidean graph. (For an Euclidean graph, the weight of each edge is given by the Euclidean distance between its two endpoints.) User input: integers k,n₁,n₂,n₃.

1. a) Write a program that takes as input the centers and the radii of three circles as follows:

1st circle: center = (125,175),r₁ = 100 +

2nd circle: center = (300,175),r₂ = 150 + 3rd circle: center = (175,325),r₃ = 125 + where is a random integer in the interval [k,k], k = user input.

Now, generate points on these circles as follows. They will serve as the vertices of the graph.

Generate the intersection points of the circles.

In addition, for each circle, generate random points lying on the circle so that two consecutive points are neither too close nor too far.

The number of points n₁,n₂,n₃ on the three circles should be taken as input during execution of your code.

1. Consider the completely connected Euclidean graph defined by the above set ofvertices, and compute its MST using Prims algorithm.
2. Save the input and the output as svg and out.svg, as shown in the figure.

Output: MST.

on which they lie. Edges are not shown for clarity.

4 Dijkstras algorithm on Euclidean graph

The task is to find single-source shortest paths for a directed Euclidean graph. (For an Euclidean graph, the weight of each edge is given by the Euclidean distance between its two endpoints.) User input: integers k,c,r,n₁,n₂.

1. Write a program that draws k circles with center c and radii r_i = ri for i =

1,2,,k.

Now, randomly generate points on these circles so that the number of points on the i-th circle lies between n₁r_i and n₂r_i. These points will serve as the vertices of the graph. Care should be taken so that for each circle, two consecutive points are neither too close nor too far.

1. For i = 1,2,,k, let P_i denote the set of random points on the i-th circle. Consider the directed Euclidean graph G(V,E), where

and .

Compute shortest paths from c to all vertices.

1. Save the input and the output as dijk-in.svg and dijk-out.svg, as shown in the figure.

Input graph (k = 4). Vertices are random points on the concentric

Output: Shortest paths from c.

circles, edges are not shown for clarity.

5 st shortest path

The task if to find a shortest path from a source s to a destination t in an Euclidean graph. (For an Euclidean graph, the weight of each edge is given by the Euclidean distance between its two endpoints.) User input: integers k,m,n,g.

1. Write a program that randomly generates k unit squares in a grid of size m n with g as the grid unit.

The corners of the squares should coincide with the grid points. The squares are basically obstacles.

The grid points are the vertices of the graph G(V,E). (p,q) is an edge of the graph if and only if the straight line segment pq does not intersect the interior of any square.

Compute a shortest path, if any, from s to t, where s is the bottom-left grid point, and t the top-right one.

1. Save the output as svg, as shown in the figure.

k = 8 k = 10

L = 1+213 8.211 L = 1+2+5+13 8.256

6 Tiling

Omino means a unit square, whereas domino means two ominoes, i.e., a rectangle of size 1 2 or 2 1.

A polyomino or n-omino is basically an axis-parallel polygon comprising n ominoes. Given an n-omino, the task is to represent it as the smallest collection of dominoes and ominoes.

User input: integers m,n(n m²).

Use the following steps for coding:

1. Generate a random n-omino in a square S of size m m The size of an omino may be 15 15 or so, and its center should be marked by a dot.

You can place the first omino at the left-bottom place of S, and then place each new omino at some random place inside S so that the new omino shares an edge with an existing omino.

Iterate until you get n ominoes.

In figure (a), n = 23, and the ominoes are numbered in the order as generated.

1. Use maximum matching in a bipartite graph to find the maximum number ofdominoes that can cover the n-omino as much as possible. Color the dominoes and the leftover ominoes as shown in figure (c).

The graph G(V,E) has V = {ominoes} and E = {(u,v) : omnio u and omino v have a common edge}.

Since this is a subgraph of a graph representing a chequer-board, it is 2-colorable and hence bipartite.

1. Save the input n-omino as svg, polyomino2.svg, and the output

as tiling.svg, as shown in figures (ac).

	S
	16	23
	13	14	11	19	15
4	5	6	9	17
			8	10
				12	20

a b c

7 Maximum line matching

1. Write a program to randomly generate m horizontal straight line segments and n vertical straight line segments with the following constraints:
   800. The endpoints should be random integers in multiples of 20 and should lieinside a rectangle R of width 1000 and height 800.
   801. The endpoints of each segment should be distinct, i.e., each segment shouldhave positive length.

• Two horizontal segments should not overlap or share an endpoint.iv) Two vertical segments should not overlap or share an endpoint.

1. v) A horizontal segment and a vertical segment should not share an endpoint.

Store the values of m,n, and the coordinates of all endpoints in a meaningful order in a txt file named hvLines.txt.

User input: m, n.

1. Write another program that reads the file txt, computes the intersection among the line segments, find the maximum matching in which each pair comprises a horizontal and a vertical segment. Save the final result as an svg file named pairs.svg, with a diamond centered at the intersection point of each pair, and showing the unmatched segments as dashed.

input output

line segments can intersect at interior points only

8 2-color intersection

1. Write a program to randomly generate m horizontal straight line segments and n vertical straight line segments with the following constraints:
   1. The endpoint coordinates should be random integers in multiples of 20 andshould lie in [20,1000].
   2. The length of each segment should be 80.iii) Two horizontal segments should not overlap or share an endpoint. iv) Two vertical segments should not overlap or share an endpoint.
   3. v) A horizontal segment and a vertical segment should not share an endpoint. vi) An intersection point cannot be any endpoint.

Store the values of m,n, and the coordinates of all endpoints in a meaningful order in a txt file named hvLines.txt.

User input: m, n.

1. Write another program that reads the file txt, computes the intersection among the line segments, and color the intersection points and endpoints using two colors (red and blue) such that no two consecutive points on the same segment get the same color.

Save the final result as an svg file named intersect.svg.

input output