Let L be a set of n lines in the plane. Give an O(nlogn) time algorithm...
Let L be a set of n lines in the plane. Give an O(nlogn) time algorithm to compute an axis-parallel rectangle that contains all the intersection points of those n lines in the plane.
Homework Answers
This is an example of Orthogonal Range Searching. The crucial observation is that any axis-parallel rectangle is uniquely identified by two of its opposing corners.Without loss of generality, we assume that the se corners are the north east and south west corners respectively. Assume that the rectangles are labeled as:A1; A2; : : : ; An. Let(six; siy)and(nix; niy) denote the southwest and northeast corners of rectangle Ai respectively .We store each rectangle in a 4 Drangetree.As per Lemma(5:9), this can be done using O(n¢log3n) storage such that the query timeisO(log4n+k), where k is the number of reported answers.
Add Answer to:
Let L be a set of n lines in the plane. Give an O(nlogn) time
algorithm...
The intersection detection problem for a set S of n line segments is to determine whether...
The intersection detection problem for a set S of n line segments is to determine whether there exists a pair of segments in S that intersect. Give a plane sweep algorithm that solves the intersection detection problem in O(nlogn) time. Prove it only requires O(nlogn) time.
8. A set of n lines are drawn in the plane. No three lines meet at a common point. No two lines a...
using induction
8. A set of n lines are drawn in the plane. No three lines meet at a common point. No two lines are na +n parallel. Then these lines divide the plane into 1 regions.
8. A set of n lines are drawn in the plane. No three lines meet at a common point. No two lines are na +n parallel. Then these lines divide the plane into 1 regions.
Consider the algorithm to find the closest pair of points in the plane. Let's say you wanted to generalize the algorithm to find the two closest pairs of points in the plane given a set of (unsor...
Consider the algorithm to find the closest pair of points in the plane. Let's say you wanted to generalize the algorithm to find the two closest pairs of points in the plane given a set of (unsorted) points (p1, py. Give an algorithm for finding the two distances for this pair. In the step to conquer the two subproblems, you must explain why your algorithm is guaranteed to find the correct result. You do not need to specify the best...
Give a randomized incremental algorithm which given n circles in the plane, reports the point with...
Give a randomized incremental algorithm which given n circles in
the plane, reports the point with greatest y coordinate that lies
inside all of the circles.
Here, "the point with greatest y coordinate that lies inside all
of the circles" means the point with greatest y coordinate among
intersection points of all circles
Please give the pseudo-code! Thank you
greatet
You are given a set of n numbers. Give an O(n^2) algorithm (NOT O(n^3), O(n^2)) to...
You are given a set of n numbers. Give an O(n^2) algorithm (NOT O(n^3), O(n^2)) to decide if there exist three numbers a, b and c are in the set such that a + b = c (Hint: sort the numbers first).
33-1 Convex layers Given a set Q of points in the plane, we define the convex...
33-1 Convex layers Given a set Q of points in the plane, we define the convex layers of Q inductively. The first convex layer of Q consists of those points in Q that are vertices of CH(O). Fori >1, define Qi to consist of the points of Q with all points in convex layers 1,2,.. .i -1 removed. Then, the ith convex layer of Q is CH(Q if Q 0and is undefined otherwise. a. Give an O(n2)-time algorithm to find...
1. a) Describe an O(m)-time algorithm that, given a set of S of n distinct numbers...
1. a) Describe an O(m)-time algorithm that, given a set of S of n distinct numbers and a positive integer k c n, determines the top k numbers in s b) Describe an O(n)-time algorithm that, given a set of S of n distinct numbers and a positive integer k < n, determines the smallest k numbers in S.
(Q4 - 30 pts: 15, 15) a) Give an O (n) time algorithm for finding the...
(Q4 - 30 pts: 15, 15) a) Give an O (n) time algorithm for finding the longest (simple) path in a tree on n vertices. Prove the correctness of your algorithm. Give a polynomial time algorithm for finding the longest (simple) path in a graph whose blocks have size bounded by a constant. Prove the correctness of your algorithm. b)
Let S be a set of disjoint simple polygons in the plane with n edges in...
Let S be a set of disjoint simple polygons in the plane with n edges in total. Prove that for any start and goal position the number of segments on the shortest path is bounded by O(n). Give an example where it is Θ(n).
Give an algorithm with the following properties. • Worst case running time of O(n 2 log(n))....
Give an algorithm with the following properties. • Worst case running time of O(n 2 log(n)). • Average running time of Θ(n). • Best case running time of Ω(1).
using induction
8. A set of n lines are drawn in the plane. No three lines meet at a common point. No two lines are na +n parallel. Then these lines divide the plane into 1 regions.
8. A set of n lines are drawn in the plane. No three lines meet at a common point. No two lines are na +n parallel. Then these lines divide the plane into 1 regions.
Consider the algorithm to find the closest pair of points in the plane. Let's say you wanted to generalize the algorithm to find the two closest pairs of points in the plane given a set of (unsorted) points (p1, py. Give an algorithm for finding the two distances for this pair. In the step to conquer the two subproblems, you must explain why your algorithm is guaranteed to find the correct result. You do not need to specify the best...
Give a randomized incremental algorithm which given n circles in
the plane, reports the point with greatest y coordinate that lies
inside all of the circles.
Here, "the point with greatest y coordinate that lies inside all
of the circles" means the point with greatest y coordinate among
intersection points of all circles
Please give the pseudo-code! Thank you
greatet
33-1 Convex layers Given a set Q of points in the plane, we define the convex layers of Q inductively. The first convex layer of Q consists of those points in Q that are vertices of CH(O). Fori >1, define Qi to consist of the points of Q with all points in convex layers 1,2,.. .i -1 removed. Then, the ith convex layer of Q is CH(Q if Q 0and is undefined otherwise. a. Give an O(n2)-time algorithm to find...
1. a) Describe an O(m)-time algorithm that, given a set of S of n distinct numbers and a positive integer k c n, determines the top k numbers in s b) Describe an O(n)-time algorithm that, given a set of S of n distinct numbers and a positive integer k < n, determines the smallest k numbers in S.
(Q4 - 30 pts: 15, 15) a) Give an O (n) time algorithm for finding the longest (simple) path in a tree on n vertices. Prove the correctness of your algorithm. Give a polynomial time algorithm for finding the longest (simple) path in a graph whose blocks have size bounded by a constant. Prove the correctness of your algorithm. b)
Most questions answered within 3 hours.
-
R2.84: There are 2 defective products in a production lot of 10.
An inspector randomly selected...
asked 33 minutes ago -
Consider the following equilibrium system: COCl2(g) CO(g) +
Cl2(g) A 10.00 L evacuated flask is filled...
asked 1 hour ago -
1) What are the two distinct steps that one needs to perform
when developing a data...
asked 1 hour ago -
2) Write a C++ program that uses a class called “Degree” to
obtain the trigonometric
values...
asked 2 hours ago -
1. In eukaryotic cells the genomes of
&
asked 2 hours ago -
The standard enthalpy of propanol (C3H7OH) is -303.0 kJ/mol.
Compute both of the
gross and net...
asked 2 hours ago -
Why PWM using H-bridge for control motor speed is more power
effiecient than the linear amplifier...
asked 2 hours ago -
In 1999, Carly Fiorina famously said,"I hope that we are at a
point that everyone is...
asked 2 hours ago -
Individuals in a species of moth vary in wing color from white to
black, but all...
asked 2 hours ago -
The following standards for variable manufacturing overhead have
been established for a company that makes only...
asked 2 hours ago -
The United States government wanted to determine what proportion
of Americans approve of the current president,...
asked 3 hours ago -
2-N stone is dropped from the top of a cliff. The stone hits the
ground 3...
asked 3 hours ago