# Questions tagged [computational-geometry]

Using computers to solve geometric problems. Questions with this tag should typically have at least one other tag indicating what sort of geometry is involved, such as ag.algebraic-geometry or mg.metric-geometry.

488
questions

1
vote

0
answers

75
views

### Finding the point within a convex n-gon that minimizes the largest angle subtended there by an edge of the n-gon

This post records a variant to the question asked in this post: Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon
Given a convex n-gon, ...

5
votes

2
answers

161
views

### Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon

For any point P in the interior of a convex polygon, the sum of the angles subtended by the edges of the polygon is obviously 2π.
Given a convex polygon, how does one algorithmically find the point (...

0
votes

0
answers

28
views

### Set of enclosed convex polyhedra in a graph

Given a straight-line graph embedded in $\mathbb{R}^3$ with known vertex coordinates and edges and no edge intersections, is it possible to find all the enclosed convex polyhedra inside? If so, is ...

0
votes

0
answers

51
views

### An algorithm to decide whether a convex polygon can be cut into 2 mutually congruent pieces

This post is based on the answer to this question: A claim on partitioning a convex planar region into congruent pieces
A perfect congruent partition of a planar region is a partition of it with no ...

1
vote

0
answers

62
views

### Algorithm to generate configurations with kissing number 12

That the kissing number of a sphere in dimension 3 is 12 is well known. However, it is also known that there is a lot of empty space between the 12 spheres. I deduce (am I wrong?) that there are many ...

0
votes

0
answers

60
views

### Computational tasks resulting from Chern-Weil theory

I have recently learned Chern-Weil theory for smooth and complex manifolds, as well as surrounding material on cohomology with integral coefficients.
I am curious what computational tasks are ...

1
vote

1
answer

59
views

### To maximize the volume of the polyhedron resulting from perimeter-halvings of a convex polygonal region

We add one more bit to Forming paper bags that can 'trap' 3D regions of max surface area (note: some possibly open related questions are also in the comments following the answer to above ...

1
vote

0
answers

90
views

### A claim on the largest area circular segment that can be drawn inside a planar convex region

This post adds a little to To find the longest circular arc that can lie inside a given convex polygon
A circular segment is formed by a chord of a circle and the line segment connecting its endpoints....

0
votes

0
answers

59
views

### Comparing partitions of a given planar convex region into pieces with equal perimeter and pieces of equal width

We continue from Cutting convex regions into equal diameter and equal least width pieces. There we had asked for algorithms to partition a planar convex polygon into (1) $n$ convex pieces of equal ...

1
vote

0
answers

75
views

### Dissection of polygons into triangles with least number of intermediate pieces

This wiki article: https://en.wikipedia.org/wiki/Wallace%E2%80%93Bolyai%E2%80%93Gerwien_theorem shows the dissection of a square into a triangle via 4 intermediate pieces. It appears easy to form a ...

2
votes

0
answers

51
views

### Computational complexity of exact computation of the doubling dimension

Given a finite metric space $X$, the doubling constant of $X$ is the smallest integer $k$ such that any ball of arbitrary radius $r$ can be covered by at most $k$ balls of radius $r/2$. The doubling ...

1
vote

0
answers

40
views

### Are there rectangles that can be cut into non-right triangles that are pair-wise similar and pair-wise non-congruent?

We generalize the questions of Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?
Can any rectangle be cut into some finite number of triangles that ...

1
vote

0
answers

89
views

### Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?

We add a bit to Tiling the plane with pair-wise non-congruent and mutually similar triangles and Cutting polygons into mutually similar and non-congruent pieces
A (non square) rectangle can obviously ...

0
votes

1
answer

55
views

### Robustness of doubling dimension to small perturbations

Let $M$ be a metric space. Then the doubling dimension of $M$, denoted $\dim M$, is defined to be the minimum value $k$ such that every ball in $M$ of radius $r$ can be covered by at most $2^k$ balls ...

2
votes

0
answers

88
views

### To find the longest circular arc that can lie inside a given convex polygon

Question: Given a convex polygonal region P, to find the longest connected subset of a circle that can lie entirely in P.
For some P, the optimal subset will be a full circle; otherwise, a single arc ...

2
votes

1
answer

250
views

### Irreducibility of an explicit complex projective variety

Let $Y\subset \mathbb P^n_\mathbb C$ be a subvariety defined by a series of homogeneous polynomials $f_1, \ldots, f_t$. Is there an effective way to determine the irreducibility of $Y$ as an algebraic ...

2
votes

0
answers

63
views

### Is this an actual solution for centroidal Voronoi tiling, or just a visual approximation? [closed]

For the capstone project at the end of my graduate Data Science studies in late 2022, I needed an algorithm that would converge to something close to centroidal Voronoi tiling, while tiling contiguous ...

0
votes

0
answers

22
views

### Smallest Semi-ellipses that contain a convex n-gon

Definition: Let us define a semi-ellipse as either of the two halves into which an elliptical region is cut by any line that passes through its center. Obviously, all semi-ellipses that come from any ...

0
votes

0
answers

47
views

### Optimal packing and covering of a triangle with squares

We continue from Another variant of the Malfatti problem.
Given a triangle T and a number n, how to cover it with n squares (of possibly different dimensions) such that the sum of the areas (...

2
votes

0
answers

119
views

### Graph Laplacians, Riemannian manifolds, and object collisions

To preface this question, I am a part-time game developer and full-time optimization fiend.
I am working on object collisions at the moment and many resources I have found online are more-or-less just ...

4
votes

2
answers

190
views

### Algorithm for grouping tetrahedra from Voronoi diagram

I have a set of 3D Voronoi generator points and their neighbouring points, which, when connected, should result in a Delaunay tetrahedralization. However, I'm having a hard time implementing this. My ...

0
votes

0
answers

61
views

### Bounds for the Dispersal Problem in convex regions

We add a bit to: Bounds for minimax facility location in a convex region
Two earlier posts: Cutting convex regions into equal diameter and equal least width pieces - 2 and Facility location on ...

1
vote

0
answers

85
views

### Bounds for minimax facility location in a convex region

An earlier question: Facility location on manifolds
A possibly related earlier post: Cutting convex regions into equal diameter and equal least width pieces - 2
The minimax facility location problem ...

3
votes

0
answers

140
views

### Algorithm to dissect a polygon into a minimum amount of rectangles, conditioned on a maximum overlap

I have the following problem, I have a problem regarding concave polygons. I want to write code to cover any polygon with a minimum amount of rectangles that are allowed to overlap and have no fixed ...

2
votes

1
answer

184
views

### Minimal degree of a polynomial such that $|p(z_1)| > |p(z_2)|, |p(z_3)|, ..., |p(z_n)|$

I was investigating the behavior of $p(x)^n \mod {q(x)}$, for some polynomials $p, q \in \mathbb{C}[x]$. We'll assume $q$ is squarefree. If $q(x) = (x - z_1) (x - z_2) (x - z_3) ... (x - z_n)$ for ...

2
votes

0
answers

92
views

### Description of a point cloud being "undersampled" wrt persistent homology, confidence level?

I am completely new to topological data analysis, so I apologise if this is a well-known area of persistent homology, as well as for any imprecise language.
Suppose we know completely the topological ...

3
votes

1
answer

129
views

### Computer program for polyhedral manifolds

Suppose I have a 3-manifold obtained via face identifications of a polyhedron (e.g. the Poincaré sphere presented as a dodecahedron with opposite faces glued). Is there a program that exists for ...

0
votes

0
answers

43
views

### Persistent diagrams for images : existing implementations or packages?

I am interest to compute the persistent diagram associated to the image of a persistent module as in ''Persistent Homology for Kernels, Images, and Cokernels'' : https://epubs.siam.org/doi/epdf/10....

0
votes

1
answer

49
views

### On largest convex m-gons contained in a given convex n-gon where m < n

This post is the inside-out variant of On smallest convex m-gons that contain a given n-gon where m<n
Given a convex n-gon region P, and an m less than n, how to find the max area convex m-gon Q ...

0
votes

0
answers

89
views

### On smallest convex m-gons that contain a given n-gon where m<n

Given a convex n-gon region P, and an m less than n, will the least area convex m-gon Q that contains P be such that an edge of Q coincides with an edge of P (in other words Q cannot be such that P ...

6
votes

1
answer

346
views

### Desargues ten point configuration $D_{10}$ in LaTeX

I want to draw the Desargues configuration $10_3$ in LaTeX using the standard picture environment, which allows only lines with the slopes $n:m$ where $\max\{|n|,|m|\}\le 6$. Is it possible? If not, ...

2
votes

0
answers

110
views

### Understanding normalization algorithms

Let $R$ be a commutative and reduced ring, finitely presented over $\mathbb Z$. Let $\overline R$ be the integral closure of $R$ in its total ring of fractions. In https://arxiv.org/abs/alg-geom/...

2
votes

1
answer

129
views

### Planar convex region maximizing the difference in 'orientation' between its smallest containing rectangle and largest contained rectangle

We say a rectangle has orientation $\theta$ if the vector from its center to the middle of its shortest side (parallel to the longest side) has some angle $\theta$ with X axis.
Consider a planar ...

1
vote

1
answer

78
views

### To optimally wrap convex laminae with paper

Ref: On folding a polygonal sheet, Multi-layered wrapping of polyhedra
Basic intent: to wrap a given convex planar lamina with a convex sheet of non-stretchable paper (such that every point on both ...

1
vote

0
answers

34
views

### On partitioning convex polygonal regions in area ratio $t : (1-t)$ where $0<t<1/2$ with least length of cut

Question: Given a convex n-gon P. How can we efficiently find the partition of P into 2 pieces with areas in the some given ratio $t : (1-t)$ where $0<t<1/2$ such that the length of cut is ...

1
vote

2
answers

109
views

### Are there variants of Euclidean Steiner Tree problem that are known to be in P?

Question: The Euclidean Steiner Tree problem (https://en.wikipedia.org/wiki/Steiner_tree_problem) is NP hard. Are there non-trivial (constrained) variants of this question that are known to have ...

1
vote

1
answer

69
views

### Partitioning polygons into obtuse isosceles triangles

Ref:
Partitioning polygons into acute isosceles triangles
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
https://math.stackexchange.com/questions/1052063/...

0
votes

0
answers

40
views

### Cutting convex polygons into affine-equivalent quadrilaterals

We continue from Tiling the plane with quadrilaterals that are mutually non-congruent and affine equivalent
Question: Can any convex polygon $C$ be partitioned into some finite number $m$ of ...

1
vote

0
answers

58
views

### Covering a unit square with odd number of equal area triangles - optimally

We add a bit to this post: Cutting off odd numbers of equal area triangles from a unit square
Question: Given an odd integer n, how does one cover the unit square completely with n equal area ...

0
votes

0
answers

42
views

### Covering triangles with mutually congruent planar regions - optimally

We continue from this old post: From a given triangle, to cut 2 mutually congruent convex pieces that together 'use' maximum area of the triangle and go from partitioning to covering.
Given ...

3
votes

2
answers

219
views

### Writing a smooth plane quartic as the vanishing of $Q_0Q_2 - Q_1^2$ for quadratic $Q_0,Q_1,Q_2$

It seems well-known that any smooth plane quartic can be written as the vanishing of $Q_0Q_2 -Q_1^2$. Is there a good way to work out these quadratic factors $Q_0,Q_1,Q_2$? For example, given the ...

3
votes

0
answers

88
views

### Fast numerical integration of $\int_{[0,\:1)^d}\left|f_x(y)-g(y)\right|^p\:{\rm d}y$ for varying $x\in[0,1)^d$

Let $k\in\mathbb N$ and $y_1,\ldots,y_k\in[0,1)^d$ with $$\frac1k\sum_{i=1}^kh(y_i)\approx\int_{[0,\:1)^d}h(y)\:{\rm d}y\tag1$$ for every nice enough function $h:[0,1)^d\to\mathbb R$.
Now let $p\ge1$, ...

1
vote

0
answers

78
views

### Counting Voronoi cells generated by lattice points

I am working on a problem in dynamical systems where I need to count Voronoi cells arising from nearest neighbours to a subset of the lattice. (See the picture below for an example: the shaded region ...

3
votes

1
answer

229
views

### Resultants and elimination theory

Consider an ideal $I = \langle f_1,\dotsc,f_n\rangle$ in the ring $k[x_1,\dotsc,x_m]$.
Define the $i$-th elimination ideal to be $I_i = I \cap k[x_{i+1},\dotsc,x_m]$.
For any two polynomials $f$ and $...

2
votes

0
answers

112
views

### Checking existence of a non-crossing Hamiltonian path in geometric graphs

I am interested in the following computational problem. Given a geometric graph (i.e, a graph drawn in the plane so that its vertices are represented by points in general position and its edges are ...

2
votes

0
answers

60
views

### Biconvex Lens - an 'oriented' convex container for planar point sets

We continue On some optimal containers of a set of points on the 2D plane.
Let us define a biconvex lens as the intersection of two circular disks - not necessarily of the same radii. Such a figure ...

0
votes

1
answer

108
views

### How many samples do you need to get constant dispersion?

Let $C_n$ be the hypercube $[-1,1]^n$. For $a_1,\cdots,a_s \in C_n$, define its dispersion $D(a_1,\cdots,a_s)$ as $\max_{x \in C_n}\min_{i \in [s]} \|x-a_i\|_{2}$. Let $0< \lambda < 1$ be a ...

17
votes

1
answer

567
views

### Aperiodic monotile in $\mathbb{R}$

Motivation. Recently a group of researchers found an aperiodic monotile in $\mathbb{R}^2$, answering a long-standing question. There are many results in higher dimensions, so let's explore the lower ...

1
vote

0
answers

64
views

### Inside-out dissections of polygons - a generalization

Definitions (Inside-out polygonal dissections): a polygon P has an inside out dissection into P' if P′ is congruent to P and the perimeter of P becomes interior to P' and so the perimeter of P' is ...

2
votes

1
answer

185
views

### Dispersion of a "random" subset of $[-1,1]^2$

Let $C$ be the square $[-1,1]^2$. Let $a_1,\dots,a_m$ be points chosen independently and uniformly at random from $C$. Let $d_m$ (dispersion) be the random variable $\max_{x \in C}{\min_{j \in [m]}{\|...