# Questions tagged [computational-geometry]

Questions about algorithmic solutions of geometric problems, or other algorithms making usage of geometry.

67 questions
Filter by
Sorted by
Tagged with
9k views

298 views

### Detecting coplanarity by given pairwise distances

Consider an undirected weighted graph $G = (V,E)$, where $V \subset \mathbb{R}^3$ so the points are 3D, and the weight of an edge equals the (Euclidean) distance between its endpoints. Note that we'...
10k views

2k views

### Find the point with minimum max distance to any point in a set

Say I have a set of points on a 2d plane, how do I find the point(s) where the maximum euclidian distance to any of the points in the set is minimized?
106 views

### Delaunay Triangulation on Convex Polytopes — Uniform Sampling

My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts: ...
321 views

### King of the North: Placing bannermen surrounding castle

I was trying to solve the King of the North problem in Kattis. Basically, the problem is, the king has a castle to protect. To do this, he wants to place bannermen across the open areas surrounding ...
1k views

### A heuristic for finding a maximum disjoint set

Background I need to find a largest set of non-overlapping axis-parallel squares, out of a given collection of candidate squares. This problem is NP-complete. Many papers suggest approximation ...
2k views

### Why are the two farthest points vertices of the Convex Hull?

I read that in a 2D space, the two points farthest away must be in the convex hull (CH). Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be a point ...