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

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

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

### 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 ...
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$ ...
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$ ...
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$ ...
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 ...
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 (...
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 ...
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 ...
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 ...
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 ...

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

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

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