Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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
  • 39k
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
  • 160k
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,572
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

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,262
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
  • 8,248
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
  • 8,248
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 ...
Rajat De's user avatar
  • 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 ...
adrianN's user avatar
  • 5,951
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
  • 160k
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

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],...
theyaoster'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
  • 160k
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,302
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
  • 8,248
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
  • 160k
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,807
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,088
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
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$. ...
stewbasic's user avatar
  • 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 ...
John L.'s user avatar
  • 39k
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. ...
HEKTO's user avatar
  • 3,088
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. ...
Yuval Filmus's user avatar
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.
Peter Taylor's user avatar
  • 2,082
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 ...
Discrete lizard's user avatar
  • 8,248

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