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 ...
- 39.1k
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.♦
- 164k
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,582
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
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,272
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$ ...
- 8,323
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$ ...
- 278k
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 ...
- 8,323
7
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 ...
- 121
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,961
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.♦
- 164k
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,646
6
votes
Finding the number of intersections of $n$ line segments with endpoints on two parallel lines
Since all points are distinct, this is a version of the Counting Inversions problem. First, sort the points $p_1, \dots, p_n$ in order of increasing $x$ coordinate to obtain an ordered list $p[1],p[2],...
- 399
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.♦
- 164k
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,424
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....
- 8,323
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.♦
- 164k
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,817
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,098
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 ...
- 278k
5
votes
How to decompose a unit cube into tetrahedra?
The simplest way is a partition into $3! = 6$ tetrahedra:
$\{x,y,z : 0 \leq x \leq z \leq y \leq 1\}$.
$\{x,y,z : 0 \leq x \leq y \leq z \leq 1\}$.
$\{x,y,z : 0 \leq y \leq x \leq z \leq 1\}$.
$\{x,y,...
- 278k
5
votes
Accepted
Can we easily check if we can place two not-intersecting circles inside a convex polygon
Let $P$ be the given polygon. Let $Q$ be the set of points inside $P$ whose distance to the boundary of $P$ is at least $r$. Your requirement can be met iff the diameter of $Q$ is at least $2r$. ...
- 268
5
votes
Accepted
Is there an algorithm to find the minimal number of dimensions, given the distances between points?
This problem of minimal dimensionality has been studied intensively.
Here is a slightly-edited excerpt from Learning metrics via discriminant kernels and multidimensional scaling: Toward expected ...
- 39.1k
5
votes
Accepted
Intersection of O(n) expanding circles with line from the origin
The solution outline:
Step 1. Verify, that all the initial (at the moment $t=0$) wave circles don't contain your starting point $(0,0)$. If yes, then continue - otherwise exit, no escape.
Step 2. ...
- 3,098
5
votes
Perpendicular vectors out of a set
The problem can be solved in time $\tilde{O}(n^{4/3})$, using several algorithms:
Agarwal, Partitioning arrangements of lines II: Applications.
Chazelle, Cutting hyperplanes for divide-and-conquer.
...
- 278k
5
votes
How can I determine if two vertices on a polygon are consecutive?
Given that the polygon is convex, its centroid $C$ is in its interior. Test the gradients of the lines $CV$ for each vertex $V$. This gives a linear time test.
- 2,092
5
votes
Accepted
How to calculate the dimension of a convex polyhedron?
While there are probably much more efficient approaches, the following method can be used to compute the dimension in polynomial time, and is not too complicated.
Implicit inequalities
The dimension ...
- 8,323
Only top scored, non community-wiki answers of a minimum length are eligible