0
votes
0answers
34 views

Can a polygon with minimal perimeter self-intersect?

Recipe. Do the following. Throw $N$ random points $(x_0,y_0),(x_1,y_1),x_2,y_2),\cdots,(x_{N-1},y_{N-1})$ in the plane.Define $(x_N,y_N)=(x_0,y_0)$ : enumeration is $\mod N$ . These points are joined ...
0
votes
0answers
51 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
1
vote
1answer
51 views

T-shaped polygons

Is there any coefficient that can indicate T-shaped polygons ? Examples of T-shaped polygons:
2
votes
1answer
404 views

Circle Packing: Unsolved Problem in Geometry?

Graham and Sloane minimize the second moment of the centres of a number discs in order to maximize their compactness. They use computational geometry techniques to find the optimal packings for ...
3
votes
0answers
120 views

How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?

I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...
3
votes
1answer
172 views

Maximizing the number of points covered by a circular disk of fixed radius.

Given a set of points in two dimensional space, and a radius r, what is the algorithm to find a disk of radius r that covers the maximum number of points?
0
votes
0answers
93 views

Does a single Gauss-Seidel iteration lead to unique coordinates?

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$, and $x,y\in\mathbb{R}^{n\times 2}$ are ...
0
votes
0answers
48 views

Maintaining the line with the 2D iterands

Suppose a linear system is given $$AX=B,$$ where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is ...
1
vote
0answers
36 views

How to discuss the maximum Area of Internal rectangular in an irregular region?

How to discuss the maximum Area of Internal rectangular in an irregular region? such as Fan-shape,or the region....
3
votes
1answer
245 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
4
votes
0answers
280 views

$3$D oriented bounding box optimization

Given: a set $S$ of points in $\mathbb{R}^3$. Find: the smallest oriented bounding box that contains all the points. Note, the bounding box is "oriented" and thus need not be axis-aligned. Can this ...