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 ...
John L.'s user avatar
  • 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.'s user avatar
  • 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 ...
OmG's user avatar
  • 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 ...
danBhentschel's user avatar
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....
Joseph O'Rourke's user avatar
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 ...
Dennis Kraft's user avatar
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$ ...
quicksort's user avatar
  • 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$ ...
Discrete lizard's user avatar
  • 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$ ...
Yuval Filmus's user avatar
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 ...
Discrete lizard's user avatar
  • 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.'s user avatar
  • 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 ...
Joseph O'Rourke's user avatar
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 ...
Sarvottamananda's user avatar
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 ...
adrianN's user avatar
  • 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.'s user avatar
  • 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,...
ratchet freak's user avatar
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.'s user avatar
  • 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 ...
Rajat De's user avatar
  • 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 ...
Vincenzo's user avatar
  • 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, ...
Wilhelm's user avatar
  • 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....
Discrete lizard's user avatar
  • 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 ...
HEKTO's user avatar
  • 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.'s user avatar
  • 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}...
user4758246's user avatar
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.'s user avatar
  • 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: ...
Joseph O'Rourke's user avatar
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 ...
aelguindy's user avatar
  • 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 ...
HEKTO's user avatar
  • 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 ...
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible