Question

In: Computer Science

A convex polygon is defined as a polygon where all its internalangles are less than...

A convex polygon is defined as a polygon where all its internal angles are less than 180 degrees and no edges cross each other. You can assume the vertex with the smallest x-coordinate (assuming origin at bottom left) is the first coordinate and other vertices are numbered in a counter-clockwise direction. Figure 1 shows an example of such a polygon where V[1] is the first polygon. For simplicity, you can also assume all polygon vertices have distinct x and y co-ordinates.

Given such a polygon, write an efficient algorithm to find:

(a) The polygon vertex with the maximum x-coordinate. Also provide the running time of the algorithm in the tightest bound possible.

(b) The polygon vertex with the maximum y-coordinate. Also provide the running time of the algorithm in the tightest bound possible.

Solutions

Expert Solution

 

Image - 1 : Which is refer in the answer for the Algorithm

Answer:

Diagram:

 

venereology answered 3 years ago
Next > < Previous

Related Solutions

(Area of a convex polygon) A polygon is convex if it contains any line segment that...
(Area of a convex polygon) A polygon is convex if it contains any line segment that connects two points of the polygon. Write a program that prompts the user to enter the number of points in a convex polygon, then enter the points clockwise, and display the area of the polygon. Sample Run Enter the number of points: 7 Enter the coordinates of the points: -12 0 -8.5 10 0 11.4 5.5 7.8 6 -5.5 0 -7 -3.5 -5.5 The...
Shallow drawing is defined as a cup drawing where the cup height is less than or...
Shallow drawing is defined as a cup drawing where the cup height is less than or equal to ________________ the diameter of the cup. ½ 1 ¼ 1 points    QUESTION 17 Clamping can be kept on the outside diameter in the case of a boring fixture even when the wall thickness is small. True False 1 points    QUESTION 18 A fixture should be designed such that the cutting tool forces act against the clamping arrangement.    True False
Prove using the principle of mathematical induction: (i) The number of diagonals of a convex polygon...
Prove using the principle of mathematical induction: (i) The number of diagonals of a convex polygon with n vertices is n(n − 3)/2, for n ≥ 4, (ii) 2n < n! for all n > k > 0, discover the value of k before doing induction
When an object is placed at a distance greater than the focal length but less than twice the focal length from a convex lense
When an object is placed at a distance greater than the focal length but less than twice the focal length from a convex lense the image is diminished.the image is virtual.All of the other choices are not correct.the image is inverted.the image is formed on the same side as theobject.For an object placed in front of a concave lense,the image is always realthe image may be erect or inverted.the image is formed on the other side of thelense.the image may be...
The potential barrier is defined by V(x) = ((A^2-(x^2)*(b^2))^0.5  where x is less than or equal to...
The potential barrier is defined by V(x) = ((A^2-(x^2)*(b^2))^0.5  where x is less than or equal to A/b. First we want to sketch V(x) Then we run a particle into it wth mass m and energy E (which is less than A). Now that we have run the particle into it we are asked to derive an expression for the probability of penetration in terms of D = E/A and sin (y) = bx/A. Finally, we are to evaluate our expression...
Geometric Optics A: Single Convex Lens Under what conditions is the magnification less than one, greater...
Geometric Optics A: Single Convex Lens Under what conditions is the magnification less than one, greater than one? What is the image distance when the object distance is twice the focal length? What is the magnification? Using the thin lens formula, explain why 1/(vertical intercept) is (or should be) the focal length of the lens? B: Lens Combination Is the final image inverted or upright? What happens to the virtual image as you move the eyepiece further from and closer...
A polygon is called convex if every line segment from one vertex to another lies entirely...
A polygon is called convex if every line segment from one vertex to another lies entirely within the polygon. To triangulate a polygon, we take some of these line segments, which don’t cross one another, and use them to divide the polygon into triangles. Prove, by strong induction for all naturals n with n ≥ 3, that every convex polygon with n sides has a trian-gulation, and that every triangulation contains exactly n − 2 triangles. (Hint: When you divide...
A polygon is called convex if every line segment from one vertex to another lies entirely...
A polygon is called convex if every line segment from one vertex to another lies entirely within the polygon. To triangulate a polygon, we take some of these line segments, which don’t cross one another, and use them to divide the polygon into triangles. Prove, by strong induction for all naturals n with n ≥ 3, that every convex polygon with n sides has a triangulation, and that every triangulation contains exactly n − 2 triangles. (Hint: When you divide...
Python Please An n-sided regular polygon has all its sides of the same length and all...
Python Please An n-sided regular polygon has all its sides of the same length and all its angles of the same degree. It is also called an equilateral and equiangular polygon. In this activity, you will design a class named RegularPolygon that contains: A private int data attribute named n that defines the number of sides of the polygon. A private float attribute named side that stores the length of the side. The constructor ( __init__ method) that creates a...
A penny stock is defined as any stock that traded for less than $5 per share....
A penny stock is defined as any stock that traded for less than $5 per share. Penny stocks are usually small, and trade infrequently. Some penny stocks trade in the exchange. Compare a penny stock with a stock which is currently included in S&P 500 index, which one would have a wider bid-ask spread? Please explain.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT