October 2008
Intermediate to advanced
368 pages
10h 9m
English
Content preview from Algorithms in a Nutshell
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
Range Queries
Given a rectangular range R defined by [xlow, ylow, xhigh, yhigh] and a set of points P, which points in P are contained within the rectangle R? A brute-force algorithm that inspects all points in P can determine the enclosed points in O(n)—can we do better? For the Nearest Neighbor problem, we organized the points into a kd-tree to process nearest neighbor queries in O(log n) time. Using the same data structure, we now show how to process Range Query problems over the Cartesian plane in
where r is the number of points reported by the query. Indeed, when the input set contains d-dimensional data points, the solution scales to solve d-dimensional Range Query problems in O(n1-1/d+r). Figure 9-24 illustrates.
Figure 9-24. Range Queries fact sheet
Input/Output
Input
A set of n points P in d-dimensional space and a d-dimensional hypercube that specifies the desired range query.
Output
The full set of points enclosed by the range query. The points do not appear in any specific order.
Assumptions
The range queries are aligned properly with the axes in the d-dimensional data set since they are specified by d individual ranges, for each dimension of the input set.
Context
Because kd-trees become unwieldy for a large number of dimensions, this algorithm and overall approach is likely ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.