# Computational Geometry and Data Structure MCQ

1. The shortest distance between a line and a point is achieved when?

a) a line is drawn at 90 degrees to the given line from the given point

b) a line is drawn at 180 degrees to the given line from the given point

c) a line is drawn at 60 degrees to the given line from the given point

d) a line is drawn at 270 degrees to the given line from the given point

Answer: a

The shortest distance between a line and a point is achieved when a line is drawn at 90 degrees to the given line from the given point.

2. What is the shortest distance between the line given by ax + by + c = 0 and the point (x1,y1)?

a) |ax1+by1+c|/√a^{2} + b^{2}

b) |ay1+bx1+c|/√a^{2} + b^{2}

c) |ax1+by1|/√a^{2} + b^{2}

d) ax1+by1+c

Answer: a

The shortest distance between a line and a point is given by the formula (ax1+by1+c)/(√a2+b2). This formula can be derived using the formula for the area of a triangle.

3. What is the shortest distance between the line given by -2x + 3y + 4 = 0 and the point (5,6)?

a) 4.5 units

b) 5.4 units

c) 4.3 units

d) 3.3 units

Answer: d

The shortest distance between a line and a point is given by the formula (ax1+by1+c)/(√a^{2}+b^{2}). Using this formula we get the answer of 3.3 units.

4. What is the general formula for finding the shortest distance between two parallel lines given by ax+by+c1=0 and ax+by+c2=0?

a) |ax1+by1+c|/√a^{2} + b^{2}

b) |c1 − c2|/√a2 + b2

c) |c1+c2|/√a2 + b2

d) c1+c2

Answer: b

The general formula for finding the shortest distance between two parallel lines given by ax+by+c1 and ax+by+c2 is (c1-c2)/(√a2+b2).

We can find this by considering the distance of any one point on one of the lines to the other line.

5. What is the distance between the lines 3x-4y+7=0 and 3x-4y+5=0?

a) 1 unit

b) 0.5 unit

c) 0.8 unit

d) 0.4 unit

Answer: d

As the given lines are parallel so the distance between them can be calculated by using the formula (c1-c2)/(√a2+b2). So we get the distance as 0.4 units.

6. What will be the slope of the line given by ax + by + c = 0?

a) -a/b

b) -b/a

c) -c/a

d) a/c

Answer: a

The slope of a line given by the equation ax + by + c=0 has the slope of -a/b. So two lines having the same ratio of the coefficient of x and y will be parallel to each other.

7. What will be the slope of the line given by 10x + 5y + 8=0?

a) -5

b) -2

c) -1.25

d) 5

Answer: b

The slope of a line given by the equation ax + by + c=0 has the slope of -a/b. So the slope of the given line will be -2.

8. What will be the coordinates of the foot of the perpendicular line drawn from the point (-1,3) to the line 3x-4y-16=0?

a) (1/5,2/5)

b) (2/25,5/25)

c) (68/25,-49/25)

d) (-49/25,68/25)

Answer: c

The foot of the perpendicular can be found by equating the distance between the two points and the distance between point and line. This is found to be (68/25,-49/25).

9. Which of the following is used to find the absolute value of the argument in C++?

a) abs()

b) fabs()

c) mod()

d) ab()

Answer: b

In C++ the absolute value of an argument can be found by using the function fabs(). It is available under the header file math. h.

10. What will be the slope of the line perpendicular to the line 6x-3y-16=0?

a) 1/2

b) -1/2

c) 2

d) -2

Answer: b

For two lines to be perpendicular the product of their slopes should be equal to -1. So as the slope of the given line is 2 so the slope of a line perpendicular to it will be -1/2.

1. Which of the following areas does the closest pair problem arise?

a) computational geometry

b) graph coloring problems

c) numerical problems

d) string matching

Answer: a

The closest pair problem arises in the two most important areas- computational geometry and operational research.

2. Which approach is based on computing the distance between each pair of distinct points and finding a pair with the smallest distance?

a) Brute force

b) Exhaustive search

c) Divide and conquer

d) Branch and bound

Answer: a

Brute force approach is based on computing the distance between each pair of distinct points and finding a pair with the smallest distance.

Brute force is a straightforward approach that solves the closest pair problem using that algorithm.

3. What is the runtime efficiency of using the brute force technique for the closest pair problem?

a) O(N)

b) O(N log N)

c) O(N^{2})

d) O(N3 log N)

Answer: c

The efficiency of the closest pair algorithm by brute force technique is mathematically found to be O(N^{2}).

4. The most important condition for which the closest pair is calculated for the points (pi, pj) is?

a) i>j

b) i!=j

c) i=j

d) i< j </j

Answer: d

To avoid computing the distance between the same pair of points twice, we consider only the pair of points (pi, pj) for which i<j.< p=”” style=”box-sizing: border-box; user-select: initial !important;”></j.<>

5. What is the basic operation of the closest pair algorithm using the brute force technique?

a) Euclidean distance

b) Radius

c) Area

d) Manhattan distance

Answer: a

The basic operation of the closest pair algorithm is Euclidean distance and its formula is given by d=√(xi-xj)2+(yi-yj)^{2}.

6. Which of the following is similar to Euclidean distance?

a) Manhattan distance

b) Pythagoras metric

c) Chebyshev distance

d) Heuristic distance

Answer: b

In older times, the Euclidean distance metric is also called a Pythagoras metric which is the length of the line segment connecting two points.

7. Which of the following strategies does the following diagram depict?

a) Divide and conquer strategy

b) Brute force

c) Exhaustive search

d) Backtracking

Answer: b

Brute force is a straight forward approach to solving critical problems. Here, we use the brute force technique to find the closest distance between p1 and p2.

8. Manhattan distance is an alternative way to define a distance between two points.

a) true

b) false

Answer: a

Manhattan distance is an alternative way to calculate distance. It is the distance between two points measured along axes at right angles.

9. What is the optimal time required for solving the closest pair problem using the divide and conquer approach?

a) O(N)

b) O(log N)

c) O(N log N)

d) O(N^{2})

Answer: c

The optimal time for solving using a divide and conquer approach is mathematically found to be O(N log N).

10. In divide and conquer, the time taken for merging the subproblems is?

a) O(N)

b) O(N log N)

c) O(N2)

d) O(log N)

Answer: b

The time taken for merging the smaller subproblems in a divide and conquer approach is mathematically found to be O(N log N).

11. The optimal time obtained through the divide and conquer approach using merge sort is the best case efficiency.

a) true

b) false

Answer: a

The optimal time obtained through the divide and conquer approach is the best class efficiency and it is given by Ω(N log N).

12. Which of the following strategies does the following diagram depict?

a) Brute force

b) Divide and conquer

c) Exhaustive search

d) Branch and bound

Answer: b

The above diagram depicts the implementation of divide and conquer. The problem is divided into sub problems and is separated by a line.

13. Which of the points are closer to each other?

a) p1 and p11

b) p3 and p8

c) p2 and p3

d) p9 and p10

Answer: c

From symmetry, we determine that the closest pair is p2 and p3. But the exact calculations have to be done using Euclid’s algorithm.

1. Cross product is a mathematical operation performed between ____________

a) 2 scalar numbers

b) a scalar and a vector

c) 2 vectors

d) any 2 numbers

Answer: c

Cross product is a mathematical operation that is performed on 2 vectors in a 3D plane. It has many applications in computer programming and physics.

2. Cross product is also known as?

a) scalar product

b) vector product

c) dot product

d) multiplication

Answer: b

A Cross product is also known as a vector product. It is a mathematical operation that is performed on 2 vectors in a 3D plane.

3. What is the magnitude of the resultant of the cross product of two parallel vectors a and b?

a) |a|.|b|

b) |a|.|b| cos(180)

c) |a|.|b| sin(180)

d) 1

Answer: c

The resultant cross product of 2 parallel vectors is always 0 as the angle between them is 0 or 180 degrees. So the answer is |a|.|b| sin(180).

4. What is the general formula for finding the magnitude of the cross product of two vectors a and b with angle θ between them?

a) |a|.|b|

b) |a|.|b| cos(θ)

c) |a|.|b| sin(θ)

d) |a|.|b| tan(θ)

Answer: c

The general formula for finding the magnitude of the cross product of two vectors is |a|.|b| sin(θ). Its direction is perpendicular to the plane containing a and b.

5. The concept of the cross product is applied in the field of computer graphics.

a) true

b) false

Answer: a

The concept of cross-product finds its application in the field of computer graphics. It can be used to find the winding of a polygon about a point.

6. Which of the following equals the a × b ( a and b are two vectors)?

a) – (a × b)

b) a.b

c) b × a

d) – (b × a)

Answer: d

The vector product an x b is equal to – (b × a). The minus sign shows that these vectors have opposite directions.

7. Cross product of two vectors can be used to find?

a) area of a rectangle

b) area of square

c) area of parallelogram

d) perimeter of a rectangle

Answer: c

Cross product of two vectors can be used to find the area of a parallelogram. For this, we need to consider the vectors as the adjacent sides of the parallelogram.

8. The resultant vector from the cross product of two vectors is _____________

a) perpendicular to any one of the two vectors involved in the cross product

b) perpendicular to the plane containing both vectors

c) parallel to any one of the two vectors involved in the cross product

d) parallel to the plane containing both vectors

Answer: b

The resultant vector from the cross product of two vectors is perpendicular to the plane containing both vectors. In other words, it should be perpendicular to both the vectors involved in the cross product.

9. What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k?

a) i + 2j + k

b) 2i + 3j + k

c) i + j – 5k

d) 2i – j – 5k

Answer: c

We can find the cross product of the given vectors by solving the determinant.

The cross product of the vectors 2i + 3j + k and 3i + 2j + k is i + j – 5k.

10. What will be the cross product of the vectors 2i + 3j + k and 6i + 9j + 3k?

a) i + 2j + k

b) i – j – 5k

c) 0

d) 2i – j – 5k

Answer: c

The cross product of the vectors 2i + 3j + k and 6i + 9j + 3k is 0.

The given vectors are parallel to each other. The cross product of parallel vectors is 0 because sin(0) is 0.

12. Which of the following operation will give a vector that is perpendicular to both vectors a and b?

a) an x b

b) a.b

c) b x a

d) both an x b and b x a

Answer: d

The resultant vector from the cross product of two vectors is perpendicular to the plane containing both vectors. So both an x b and b x a will give a vector that is perpendicular to both vectors a and b.

1. ___________ is a method of constructing the smallest polygon out of n given points.

a) closest pair problem

b) quick hull problem

c) path compression

d) union-by-rank

Answer: b

- Quick hull is a method of constructing the smallest convex polygon out of n given points in a plane.
- Quickhull is a method of computing the convex hull of a finite set of points in the plane.
- It uses a divide and conquer approach similar to that of quicksort, from which its name derives.

2. What is the other name for quick hull problem?

a) convex hull

b) concave hull

c) closest pair

d) path compression

Answer: a

The other name for the quick hull problem is the convex hull problem whereas the closest pair problem is the problem of finding the closest distance between two points.

3. How many approaches can be applied to solve the quick hull problem?

a) 1

b) 2

c) 3

d) 4

Answer: b

Most commonly, two approaches are adopted to solve the quick hull problem- the brute force approach and the divide and conquer approach.

4. What is the average case complexity of a quick hull algorithm?

a) O(N)

b) O(N log N)

c) O(N2)

d) O(log N)

Answer: b

The average case complexity of the quick hull algorithm using the divide and conquer approach is mathematically found to be O(N log N).

5. What is the worst-case complexity of a quick hull?

a) O(N)

b) O(N log N)

c) O(N^{2})

d) O(log N)

Answer: c

The worst-case complexity of the quick hull algorithm using the divide and conquer approach is mathematically found to be O(N^{2}).

6. What does the following diagram depict?

a) closest pair

b) convex hull

c) concave hull

d) path compression

Answer: b

The above diagram is a depiction of a convex hull, also known as a quick hull since it encloses n points into a convex polygon.

7. Which of the following statement is not related to the quick hull algorithm?

a) finding points with minimum and maximum coordinates

b) dividing the subset of points by a line

c) eliminating points within a formed triangle

d) finding the shortest distance between two points

Answer: d

Finding the shortest distance between two points belongs to the closest pair algorithm while the rest is quickhull.

8. The quick hull algorithm runs faster if the input uses non-extreme points.

a) true

b) false

Answer: a

It is proved that the quick hull algorithm runs faster if the input uses non-extreme points and also if it uses less memory.

9. To which type of problems does quick hull belong to?

a) numerical problems

b) computational geometry

c) graph problems

d) string problems

Answer: b

- Quickhull is a method of computing the convex hull of a finite set of points in the plane.
- It uses a divide and conquer approach similar to that of quicksort, from which its name derives.
- Quick hull problems and closest pair algorithms are some of the examples of computational problems.

10. Which of the following algorithms is similar to a quick hull algorithm?

a) merge sort

b) shell sort

c) selection sort

d) quick sort

Answer: d

- Quickhull algorithm is similar to a quick sort algorithm with respect to the run time average case and worst case efficiencies.
- Quick hull problems and closest pair algorithms are some of the examples of computational problems.

11. Who formulated the quick hull algorithm?

a) Eddy

b) Andrew

c) Chan

d) Graham

Answer: a

Eddy formulated a quick hull algorithm. Graham invented the graham scan. Andrew formulated Andrew’s algorithm and Chan invented Chan’s algorithm.

12. The time taken to find the ‘n’ points that lie in a convex quadrilateral is?

a) O(N)

b) O(N log N)

c) O(N2)

d) O(log N)

Answer: a

The time taken to find the ‘n’ points that lie in a convex quadrilateral is mathematically found to be O(N).

1. Chan’s algorithm is used for computing _________

a) Closest distance between two points

b) Convex hull

c) Area of a polygon

d) Shortest path between two points

Answer: b

Chan’s algorithm is an output-sensitive algorithm used to compute the convex hull set of n points in a 2D or 3D space. The closest pair algorithm is used to compute the closest distance between two points.

2. What is the running time of Chan’s algorithm?

a) O(log n)

b) O(n log n)

c) O(n log h)

d) O(log h)

Answer: c

The running time of Chan’s algorithm is calculated to be O(n log h) where h is the number of vertices of the convex hull.

3. Who formulated Chan’s algorithm?

a) Timothy

b) Kirkpatrick

c) Frank Nielsen

d) Seidel

Answer: a

Chan’s algorithm was formulated by Timothy Chan. Kirkpatrick and Seidel formulated the Kirkpatrick-Seidel algorithm. Frank Nielsen developed a paradigm relating to Chan’s algorithm.

4. The running time of Chan’s algorithm is obtained by combining two algorithms.

a) True

b) False

Answer: a

The O(n log h) running time of Chan’s algorithm is obtained by combining the running time of Graham’s scan [O(n log n)] and Jarvis match [O(nh)].

5. Which of the following is called the “ultimate planar convex hull algorithm”?

a) Chan’s algorithm

b) Kirkpatrick-Seidel algorithm

c) Gift wrapping algorithm

d) Jarvis algorithm

Answer: b

The Kirkpatrick-Seidel algorithm is called the ultimate planar convex hull algorithm. Its running time is the same as that of Chan’s algorithm (i.e.) O(n log h).

6. Which of the following algorithms is the simplest?

a) Chan’s algorithm

b) Kirkpatrick-Seidel algorithm

c) Gift wrapping algorithm

d) Jarvis algorithm

Answer: a

Chan’s algorithm is very practical for moderate-sized problems whereas the Kirkpatrick-Seidel algorithm is not. Although, they both have the same running time. The gift wrapping algorithm is a non-output sensitive algorithm and has a longer running time.

7. What is the running time of the Hershberger algorithm?

a) O(log n)

b) O(n log n)

c) O(n log h)

d) O(log h)

Answer: b

Hershberger’s algorithm is an output-sensitive algorithm whose running time was originally O(n log n). He used Chan’s algorithm to speed up to O(n log h) where h is the number of edges.

8. Which of the following statements is not a part of Chan’s algorithm?

a) eliminate points, not in the hull

b) recompute convex hull from scratch

c) merge previously calculated convex hull

d) reuse convex hull from the previous iteration

Answer: b

Chan’s algorithm implies that the convex hulls of larger points can be arrived at by merging previously calculated convex hulls. It makes the algorithm simpler instead of recomputing every time from scratch.

9. Which of the following factors account more for the cost of Chan’s algorithm?

a) computing a single convex hull

b) locating points that constitute a hull

c) computing convex hull in groups

d) merging convex hulls

Answer: c

The majority of the cost of the algorithm lies in the pre-processing (i.e.) computing convex hull in groups. To reduce cost, we reuse convex hulls from previous iterations.

10. Chan’s algorithm can be used to compute the lower envelope of a trapezoid.

a) true

b) false

Answer: a

An extension of Chan’s algorithm can be used for proving solutions to complex problems like computing the lower envelope L(S) where S is a set of ‘n’ line segments in a trapezoid.