# 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
Filter by
Sorted by
Tagged with
1 vote
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,483
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 (...
• 5,483
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 ...
• 1
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 ...
• 5,483
1 vote
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 ...
• 111
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
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 ...
• 5,483
1 vote
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....
• 5,483
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 ...
• 5,483
1 vote
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 ...
• 5,483
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
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 ...
• 5,483
1 vote
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 ...
• 5,483
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 ...
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 ...
• 5,483
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 ...
• 279
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 ...
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 ...
• 5,483
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 (...
• 5,483
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 ...
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 ...
• 142
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 ...
• 5,483
1 vote
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 ...
• 5,483
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 ...
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,979
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 ...
• 21
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 ...
• 155
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....
• 73
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 ...
• 5,483
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 ...
• 5,483
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, ...
• 40.9k
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/...
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 ...
• 5,483
1 vote
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 ...
• 5,483
1 vote
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 ...
• 5,483
1 vote
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 ...
• 5,483
1 vote
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/...
• 5,483
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 ...
• 5,483
1 vote
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 ...
• 5,483
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 ...
• 5,483
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 ...
• 469
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$, ...
• 161
1 vote