# Questions tagged [computational-geometry]

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

226 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0answers
641 views

### Largest set of cocircular points

Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior). This can be done in $O(n^3)$ ...
0answers
102 views

### Data Structures for Non-Orientable Manifolds

I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, ...
0answers
2k views

### Area of the union of rectangles anchored on the x-axis

I am trying to solve the following computational geometry problem. Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the $x$-axis....
0answers
198 views

### Algorithms for curve construction

I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks? ...
0answers
113 views

### Placing a tripod in a plane such that it partition a given set of points (with pic)

I would appreciate if anyone could help me with the following problem: Given a set of 3n points in the plane with n > 0, is it possible to find a placement of a tripod such that each region contains ...
0answers
98 views

### $3$-dimensional convex hull using only a desired number of planes

I would like to find the convex polytope with the smallest volume that envelops (contains) all the points of a given 3D point cloud and that can be constructed from only $k$ planes. This is similar to ...
0answers
223 views

### Extrema and saddle point of 3D field at different scales

I have a scalar 3D field $f(x, y, z)$ with $x,y,z$ on a regular grid. I would like to know the location of the maxima, minima, saddle points and their relation as a function of a smoothing scale. For ...
0answers
555 views

### Space filling between random 2D lines

Note that I had asked this question in GIS forum, although it has gotten many up-votes, still has not received any answer. Hope you can break the silence, some collaboration :) Consider a region (...
1answer
311 views

### Radon transform for advanced 3d graphics and games?

The Radon transform is used to take 2d projections of an object and create a 3d representation. It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly ...
0answers
36 views

### Efficient algorithm to compute the Heesch number of a shape

The Heesch number of a shape is the maximum number of layers of copies of the same shape that can surround it. For example the following shape (in the center) has a Heesch number of 4, because we can ...
0answers
132 views

### Finding the Hamiltonian cycle that uses the least amount of straight lines

How can i find the Hamiltonian cycle on an nxn grid that uses the least amount of stright lines (curves left/right as much as possible)? Here's an example we have devised for 8x8: Here is an example ...
0answers
142 views

0answers
59 views

### How to check whether a lattice polytope embeds into another lattice polytope?

Suppose I have two polytopes $P\subset \mathbb R^m$ and $Q\subset \mathbb R^n$ with vertices with integral coordinates. How do I check whether $P$ is embeddable into $Q$? More precisely, "...
0answers
31 views

### A simple algorithm to solve the MST Sensitivity Analysis problem in linear time when the MST is a path

The problem. Given an undirected, connected, edge-weighted graph $G=(V, E_G; w)$ and a minimum spanning tree (MST) $T=(V, E_T)$ of $G$, the MST sensitivity analysis problem asks to find, for each ...
0answers
63 views