# Tag Info

### 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

### 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 ...
• 164k

### 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
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....
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
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
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
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
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
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
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 ...
• 164k

### 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

• 278k
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
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
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

### 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

### 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