33
votes
What is this data structure/concept where a plot of points defines a partition to a space
What you described is Voronoi diagram.
Here is an excerpt from Wikipedia.
In the simplest case, shown in the first picture, we are given a finite set of points ${p_1, \cdots, p_n}$ in the Euclidean ...
- 38.6k
13
votes
Closest pair of points between two sets, in 2D
Yes, this can be $O(n \log n)$ time. Build a Voronoi diagram for $T$. Then, for each point $s \in S$, find which cell of the Voronoi diagram it is contained in. The center of that cell is the point ...
D.W.♦
- 156k
12
votes
How can I determine if two vertices on a polygon are consecutive?
As the polygon is convex, it is simple! Two vertices are consecutive if all other vertices are located on the same side of the line that goes through these two points. This means that the cross ...
- 3,562
11
votes
Accepted
Sort a list of points to form a non-self-intersecting polygon
Thanks to the advice of Rick Decker, I was able to create an algorithm based on the first half of the Grahm Scan convex hull algorithm, as detailed here.
The first step of the Grahm Scan is to sort ...
- 301
11
votes
Accepted
Find a straight line to divide two convex polygons by equal area
This is known as the Ham-Sandwich theorem:
Given two measurable objects in $2$-dimensional Euclidean space, it is possible to divide each of them in half with a line.
Note: Convexity is not needed....
- 854
9
votes
Accepted
guillotine cuts versus general cuts
Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts.
Let us start with the upper bound and assume we are ...
- 618
9
votes
Accepted
How generate n equidistant points in a n-1 dimensional space
I assume we are working in $\mathbb{R}^n$.
First of all, observe that one regular $n-$simplex effectively determines all the others. In fact, if $S_1, S_2$ are two sets of points in $\mathbb{R}^n$ ...
- 4,222
8
votes
Accepted
Queries to count points lying on arbitrary line
Note that via point-line duality (i.e. mapping each point $(p_x,p_y)$ to the line $y=p_x x - p_y$ and each line $y=mx +c$ to the point $(m,-c)$), this problem is equivalent to: given a set $L$ of $n$ ...
- 7,768
7
votes
Accepted
Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1)
Here is a proof sketch from Robins and Salowe, On the Maximum Degree of Minimum Spanning Trees. Let $x$ be some vertex in the MST. We want to show that its degree $d$ is small.
Let $y_1,\ldots,y_d$ ...
- 275k
7
votes
Accepted
King of the North: Placing bannermen surrounding castle
This appears to be a max-flow/min-cut problem. Consider the directed graph $G$ with all non-hill/wall squares as vertices and edges between the neighbouring non-hill/wall cells in the map.
As the ...
- 7,768
6
votes
Accepted
Given a moving ball in a grid, which squares does the ball reach?
Exhaustively tracing the movement of the ball is the easiest to program, and also not too bad on efficiency grounds. You should keep a hash table of all states of the ball that have been seen before (...
D.W.♦
- 156k
6
votes
Accepted
Partial polygon matching
There is quite a bit of work on this important problem. Some of the most
insightful work is by Helmut Alt and collaborators. He wrote a survey in 2009:
Helmut Alt. "The computational geometry of ...
- 854
6
votes
Accepted
Finding a way out of a polygon
Basically this is shortest path problem in polygon with holes. There is no constraint in taking $E_i$ as a path of negligible width.
If you just want to connect internal holes to outside boundary ...
- 4,807
6
votes
Accepted
Generate random point inside a polyhedron
If you polytope is convex, this answer should work. Otherwise you can always do rejection sampling: Sample a point from the bounding box, check whether it's inside the polygon. That gets really slow ...
- 5,931
6
votes
Accepted
Minimize number of circles to cover set of points
Set Cover
If you restrict the possible center points of the circles to be the set of points, then this is an instance of set cover where the universe has $|P| \le 1000$ elements and where each set ...
D.W.♦
- 156k
6
votes
How generate n equidistant points in a n-1 dimensional space
You can make n-1 equidistant points by using the unit vectors along each of the axis aka. (1, 0, 0, 0, ..., 0); (0, 1, 0, 0, ..., 0); (0, 0, 1, 0, ..., 0); etc., The last nth point will be along the 1,...
- 4,301
6
votes
What if the travelling salesman travelled by plane?
I suggest you read more about the Traveling Salesman Problem. All of your questions are answered in other standard references (such as the Wikipedia link I gave). No, the greedy algorithm is not ...
D.W.♦
- 156k
6
votes
Accepted
Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime.
Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose ...
- 111
6
votes
Accepted
Difference between convex hull algorithms
If $n$ is the number of 2D points, let $h \le n$ be the number of points on the convex hull. Then:
Gift wrapping takes time $\Theta(n h)$, which can be $\Theta(n^2)$ in the worst case. It is ...
- 3,252
6
votes
What edges are not in a Gabriel graph, yet in a Delauney graph?
Ah, I think I figured it out, thanks to the help from Discrete Lizard.
See the following image of a Delaunay triangulation, where I've highlighted one example where the edges would be included in DT, ...
- 123
6
votes
Accepted
Multi-line fitting problem
The general case of this problem is NP-complete, as shown by Meggido and Tamir [N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane. Oper. Res. Lett., 1:194–197, 1982....
- 7,768
5
votes
Accepted
Complexity for finding a ball that maximizes the number of points lying in it
It looks like a sublinear algorithm for the Ball Range Counting Problem isn't known for now.
However, if you could accept a non-exact answer then you could approximate a disk by a set of squares with ...
- 3,048
5
votes
Accepted
How can I sum pixel values over a rotated rectangle?
One simple technique that's probably not optimal, but is better than naively enumerating all pixels in the rotated rectangle, is to use "integral columns" (thanks to Yves Daoust for the name):
...
D.W.♦
- 156k
5
votes
Accepted
Closest pair of points in a Plane
No, your approach will not work
Let $O$ be your chosen origin. Let $A$, $B$ be two of your other points. $OAB$ form a triangle.
The vector you have in mind would contain the distances $\overline{OA}...
- 418
5
votes
Accepted
Algorithm to enclose a 2D-gridbased-room efficient
This is a graph cut problem.
Build a graph with one vertex per square. Add an edge between each pair of adjacent vertices (i.e., where you can go from one to the other in a single step). Add an ...
D.W.♦
- 156k
5
votes
Accepted
Finding a minimal width strip which encloses a set of points in the plane
Take the convex hull of your set of points. Then use "rotating calipers" to
find the optimal strip.
What is needed here to make this work is a lemma that characterizes a
potentially optimal solution: ...
- 854
5
votes
Closest pair of points between two sets, in 2D
I am expanding my comment into an answer, since I figured out a semi-satisfactory answer. This only solves the problem for $L^1$-distance. This answer is basically wrong.
This paper solves the ...
- 1,787
5
votes
Accepted
Data structure for adjacent rectangles
The sweeping algorithm, suggested by @adrianN, can be elaborated this way.
Step 1. Put all your rectangles in a map of sets in such way, that:
the map key is left boundary of rectangle
the map value ...
- 3,048
5
votes
Accepted
Complexity of determining whether three points are collinear from a set of points
There is an $O(n^2)$ algorithm for the more general problem of minimum area triangle, see for example these lecture notes. The problem itself (as well as minimum area triangle) is 3SUM-hard, as shown ...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible