1. 1d range search
-- Range search: find all keys between k1 and k2.
-- Range count: number of keys between k1 and k2.
-- BST Implementation of range count: rank(k) -- number of keys < k (Running time : O(logN)
public int size(Key lo, Key hi) { if (contains(hi)) return rank(hi) - rank(lo) + 1; else return rank(hi) - rank(lo); }
-- BST Implementation of range search: (Running time : O(R + NlogN)
-- Recursively find all keys in left subtree (if any could fall in range).
-- Check key in current node.
-- Recursively find all keys in right subtree (if any could fall in range).
2. Orthogonal line segment intersection
-- Given N horizontal and vertical line segments, find all intersections.
-- Assumption: All x- and y-coordinates are distinct.
3. Sweep-line Algorithm
-- Algorithm:
-- x-coordinates define events.
-- h-segment (left endpoint): insert y-coordinate into BST.
-- h-segment (right endpoint): remove y-coordinate from BST.
-- v-segment: range search for interval of y-endpoints.
-- Running Time:
-- Put x-coordinates on a PQ (or sort). ---- N log N
-- Insert y-coordinates into BST. ---- N log N
-- Delete y-coordinates from BST. ---- N log N
-- Range searches in BST. ---- N log N + R
-- Reduces 2d orthogonal line segment intersection search to 1d range search.
4. 2-d orthogonal range search:
-- Extension of ordered symbol-table to 2d keys.
-- Insert a 2d key.
-- Delete a 2d key.
-- Search for a 2d key.
-- Range search: find all keys that lie in a 2d range.
-- Range count: number of keys that lie in a 2d range.
-- Geometric interpretation.
-- Keys are point in the plane.
-- Find/count points in a given horizontal-vertical rectangle
5. Grid implementation
-- Algorithm
-- Divide space into M-by-M grid of squares.
-- Create list of points contained in each square.
-- Use 2d array to directly index relevant square.
-- Insert: add (x, y) to list for corresponding square.
-- Range search: examine only squares that intersect 2d range query.
-- Space-time tradeoff.
-- Space: M^2 + N.
-- Time: 1 + N / M^2 per square examined, on average.
-- Grid square size too small: wastes space.
-- Grid square size too large: too many points per square.
-- Rule of thumb: √N-by-√N grid.
-- Running time. [if points are evenly distributed and M ~ √N ]
-- Initialize data structure: N.
-- Insert point: 1.
-- Range search: 1 per point in range.
-- Clustering : a well-known phenomenon in geometric data.
-- Lists are too long, even though average length is short.
-- Need data structure that adapts gracefully to data.
6. Space-partitioning trees:
-- Use a tree to represent a recursive subdivision of 2d space.
-- Implementation : BST, but alternate using x- and y-coordinates as key.
-- Search gives rectangle containing point.
-- Insert further subdivides the plane.
-- Range search in a 2d tree : (Running time : typical case : R + log N , worst case : R + √N)
-- Check if point in node lies in given rectangle.
-- Recursively search left/bottom (if any could fall in rectangle).
-- Recursively search right/top (if any could fall in rectangle).
-- Nearest neighbor search in a 2d tree : (Running time : typical case : log N , worst case : N)
-- Check distance from point in node to query point.
-- Recursively search left/bottom (if it could contain a closer point).
-- Recursively search right/top (if it could contain a closer point).
-- Organize method so that it begins by searching for query point.
7. Kd tree ---- Recursively partition k-dimensional space into 2 halfspaces.
-- Implementation: BST, but cycle through dimensions ala 2d trees.
8. 1d interval search
-- Data structure to hold set of (overlapping) intervals.
-- Insert an interval ( lo, hi ).
-- Search for an interval ( lo, hi ).
-- Delete an interval ( lo, hi ).
-- Interval intersection query: given an interval ( lo, hi ), find all intervals in data structure overlapping ( lo, hi ).
9. Interval search trees
-- Create BST, where each node stores an interval ( lo, hi ).
-- Use left endpoint as BST key.
-- Store max endpoint in subtree rooted at node.
-- To insert an interval ( lo, hi ) :
-- Insert into BST, using lo as the key.
-- Update max in each node on search path.
-- To search for any one interval that intersects query interval ( lo, hi ) :
-- If interval in node intersects query interval, return it.
-- Else if left subtree is null, go right.
-- Else if max endpoint in left subtree is less than lo, go right.
-- Else go left.
-- Running Time :
10. Proof of correctness of Interval Search :
-- Case 1. If search goes right, then no intersection in left.
-- Left subtree is empty ⇒ trivial.
-- Max endpoint max in left subtree is less than lo ⇒ for any interval (a, b) in left subtree of x, we have b ≤ max < lo.
-- Case 2. If search goes left, then there is either an intersection in left subtree or no intersections in either.
-- Suppose no intersection in left. Since went left, we have lo ≤ max. Then for any interval (a, b) in right subtree of x, hi < c ≤ a where c is the left endpoint of interval with max right endpoint ⇒ no intersection in right.
11. Orthogonal rectangle intersection:
-- Goal. Find all intersections among a set of N orthogonal rectangles.
-- Sweep Line Algorithm:
-- Sweep vertical line from left to right.
-- x-coordinates of left and right endpoints define events.
-- Maintain set of rectangles that intersect the sweep line in an interval search tree (using y-intervals of rectangle).
-- Left endpoint: interval search for y-interval of rectangle: insert y-interval.
-- Right endpoint: remove y-interval.
-- Running Time :
-- Put x-coordinates on a PQ (or sort). ---- N log N
-- Insert y-intervals into ST. ---- N log N
-- Delete y-intervals from ST. ---- N log N
-- Interval searches for y-intervals. ---- N log N + R log N
-- Reduces 2d orthogonal rectangle intersection search to 1d interval search.
12. Summary:
相关推荐
ArborX ArborX是一个开放源代码库,旨在提供性能可移植的几何搜索算法,类似于nanoflann和Boost Geometry。安装可以在找到安装说明。使用ArborX 该接口描述。问题,错误报告和问题跟踪问题,错误报告和问题跟踪由...
image matching and recognition with local features Correspondence Semi-local and global geometric relations Ransac and Hough Transform
17.1 Robust Geometric Primitives 17.2 Convex Hull 17.3 Triangulation 17.4 Voronoi Diagrams 17.5 Nearest Neighbor Search 17.6 Range Search 17.7 Point Location 17.8 Intersection Detection 17.9 ...
4. **混合索引方法**:结合多种技术的优点,如Multi Vantage Point Tree、Geometric Near-neighbor Access Tree等。 5. **近似相似性搜索方法**:如BBD树、Buoy Indexing等。 通过以上概述可以看出,相似性搜索是一...
segment an image, and track an object in a live videoRecognize an object in an image and build a visual search engineReconstruct a 3D map from imagesBuild an augmented reality application, In Detail,...
原pdf书签不正常(非发行版pdf),2016.02.16本人对书签进行了... Recognize an object in an image and build a visual search engine Reconstruct a 3D map from images Build an augmented reality application
segment an image, and track an object in a live videoRecognize an object in an image and build a visual search engineReconstruct a 3D map from imagesBuild an augmented reality application, In Detail,...
简化图神经网络的架构搜索 概述 ...3. The implementations of Random and Bayesian search algorithms. 要求 需要最新版本的Pytorch-geometric(PyG)。 更多细节可以在找到 Python == 3.7.4 Pyto
(您可以为此使用extend_search_path.m脚本)。 您还将需要在MATLAB File Exchange上提供各种可用的库,所有这些库都必须在MATLAB PATH 。 这些库包含在源代码中,无需下载。 该库是不受这个仓库的许可证。 如果您...
(https://www.spoonflower.com/tags/geometric)------------------------------添加键盘快捷键1)转到chrome:// extensions / 2)单击键盘快捷键(在页面底部附近)3)将键盘快捷键设置为cmd + shift + F(或您的...
Events happen in a one-dimensional geometric space, so locations are given by a single real number \( x \) as a coordinate on the x-axis. - **Signal Propagation**: Signals can travel at most at the ...
This is why MT has proved to be extremely useful in various spoken and written text applications in reducing language barriers and facilitating cross- lingual information search as well as commerce ...
Many visual search and matching systems represent images using sparse sets of “visual words”: descriptors that have been quantized by assignment to the best-matching symbol in a discrete vocabulary....
However, the inherent difficulty in solving this problem, which stems from the high dimensionality of the search space, the geometric and kinematic properties of the obstacles, the cost function to ...
( def search ( create-search-fn { :cache-method clojure.core.memoize/memo :depth 15 :tile-size 64 })) ; ; let's create some geometric shapes ( require '[cljts.geom :as g]) ( require '[cljts.analy
算法导论,英文 【本书目录】 I Foundations Introduction 3 ...C.4 The geometric and binomial distributions 1112 C.5 The tails of the binomial distribution 1118 Bibliography 1127 Index 1145
We will discuss how to use this knowledge to build a visual search engine. Chapter 10, Augmented Reality, shows how to build an augmented reality application. By the end of this chapter, you will be ...
which try to seek the the largest margin with the geometric constraints. The improvement of the SVM algorithm in the title is that converse the quadratic programming inequality constraints to the ...