Suppose we are given a range searching data structure D that can answer rangesearching queries for a set of n points in d dimensional space for any fixed dimension d (like 8, 10, or 20) in time that is O(logd n k), where k is the number of answers Show how to use D to answer the following queries for a set S of n rectangles in the plane findAllContaining(x, y) Return an enumeration of all rectangles in S that contain the point (x, y) findAllIntersecting(a, b, c, d) Return an enumeration of all rectangles that intersect the rectangle with x range a, b and y range c, d What is the running time needed to answer each of these queries

Question: Suppose we are given a range-searching data structure D that can answer rangesearching queries for a set of n points in d-dimensional space for any

Suppose we are given a range-searching data structure D that can answer rangesearching queries for a set of n points in d-dimensional space for any fixed dimension d (like 8, 10, or 20) in time that is O(logd n+k), where k is the number of answers. Show how to use D to answer the following queries for a set S of n rectangles in the plane:

findAllContaining(x, y): Return an enumeration of all rectangles in S that contain the point (x, y).
findAllIntersecting(a, b, c, d): Return an enumeration of all rectangles that intersect the rectangle with x-range [a, b] and y-range [c, d].

What is the running time needed to answer each of these queries?

Step by Step Solution

★★★★★

3.43 Rating (166 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

The running time needed to answer findAllContainingxy is Olog2 n k where k is the number of answers ... View full answer

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Data Structures Algorithms Questions!

Suppose we are given two sequences A and B of n integers, possibly containing duplicates, in the range from 1 to 2n. Describe a linear-time algorithm for determining if A and B contain the same set...

Suppose that we are given a set of n objects, where the size si of the i th object satisfies 0

In some computer graphics and computer gaming applications, in order to save space, we might like to store a set of two-dimensional points in a single data structure that can be used for both...

ANSI-SPARC6 Programming Language Compilation Write notes on each of the following topics: (a) the implementation of labels and jumps in a recursive, block structured programming language [7 marks]...

Hi, math experts. I am recently learning from Pattern Recognition and Machine Learning, Chris Bishop. Please provide a detailed explainations briefly for the following sections. 1. Section 1.2.2...

Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...

A discrete sequence {xn} can be converted into a continuous representation x(t) = ts X n= (t n ts) xn, where ts is the sampling period. (a) State two characteristic properties of Dirac's function. [2...

Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...

PLEASE COMPLETE NO LATER THAN 10/07 @8:00AM Each question(1,2,& 3) must be a minimum of 200 words. Please make answers detailed and knowledgeable based off the attached reading. ARE YOU ABLE TO...

In a Hopfield neural network configured as an associative memory, with all of its weights trained and fixed, what three possible behaviours may occur over time in configuration space as the net...

Find a survey on the internet that includes 1015 questions. write a paper of approximately 750 words that addresses the following: summarizes the topic and survey participants. describes the survey...

Is it important in the schistosomiasis study for all 20 mice to come from the same population of mice? Why or why not?

Which of the following would eliminate scarcity as an economic problem? a. Moderation of peoples competitive instincts. b. Discovery of large new energy reserves. c. Resumption of steady productivity...

=+2. Which of the generic strategies does Lego appear to be using based on this case? Provide support for your choice.

Given two values X and Y. You need to convert X to Y by performing various steps. In a step, we can either multiply 2 to the value or subtract 1 from it. You need to display the number of steps and...

Converting Decimal Numbers to Binary Numbers using stack data structure. store reminders into the stack and then print the stack.

Find the middle element in a singly linked list. Tell the complexity of your solution. First solution: Find the length of linked list. Then find the middle element and return it. Second solution: Use...

Points: 0 of 6 Save Assume that the sample is a simple random sample obtained from a normally distributed population of IQ scores of statistics professors. Use the table below to find the minimum...

Please complete questions and show work with problems please and thank you in advance 1. Determine whether the data described are continuous, discrete, nominal or ordinal: a) (2 points) Brands of...

First Simple Bank pays 9.2 percent simple interest on its investment accounts. First Complex Bank pays interest on its accounts compounded annually. Required: What rate should the bank set if it...