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.
521 questions
3 votes
1 answer
218 views
On partitioning convex polygons into kites
A kite is a quadrilateral with reflection symmetry across a diagonal. A kite with two opposite angles right is a right kite. If a pair of angles in a kite are equal and acute (obtuse), we may say the ...
- 7,221
11 votes
1 answer
649 views
Outside-the-box in 3D: can the $27$ vertices of $\{0,1,2\}^3$ be visited with $13$ line segments connected at their endpoints, without repetition?
This is a variant of the 3D generalization of the well-known Thinking outside the box Nine dots problem I discussed in my previous MO post Optimal covering trails for every $k$-dimensional cubic ...
- 1,905
0 votes
0 answers
104 views
Ham-sandwich cut for pseudo configuration of points
I have the following question regarding a generalization of the classical theorem of 'Ham-Sandwich Cut' for pseudo point-configuration. First, a few definitions. A collection of continuous curves in ...
- 1,435
3 votes
2 answers
243 views
Computing the graded Betti numbers of $S$-modules
Does anybody know of any good resources on techniques used to compute the graded Betti numbers of an $S$-module $M$ that is the quotient of $S$ by a homogeneous ideal? (Here $S$ denotes a polynomial ...
- 53
4 votes
0 answers
120 views
To cover the surface of a cube with mutually congruent planar convex regions
Ref: To partition the surface of a cube into connected congruent sets On finding optimal convex planar shapes to cover a given convex planar shape Question: Given a positive integer $n$, we need to ...
- 7,221
2 votes
0 answers
122 views
To partition the surface of a cube into connected congruent sets
Question: Given an integer $n$, we want to divide the surface of a cube into $n$ connected and mutually congruent point sets. The congruence is in the sense that the sets are congruent planar regions ...
- 7,221
1 vote
0 answers
43 views
Planar Convex Hull given oracle confiming shape
Given two intervals $ X = [x_{min}, x_{max}], Y = [y_{min}, y_{max}]$ and an function $f: X\times Y\rightarrow \{0,1\}$ which confirms, whether a point is in or out of an unknown $k$-sided geometric ...
- 11
6 votes
2 answers
249 views
Convex polygons that tile convex polygons with less number of sides
Ref: On non-convex polygons that tile convex polygons Triangles that can be cut into mutually congruent and non-convex polygons https://erich-friedman.github.io/mathmagic/0499.html Question: Apart ...
- 7,221
9 votes
1 answer
487 views
Decide if a pair of equal area triangles can be dissected into each other via some set of finitely many equal area pieces
Given two equal area triangles, how does one decide if both can be cut into the same set of finitely many pieces with all pieces having the same area? Does allowing the pieces to be non-convex have ...
- 7,221
3 votes
1 answer
251 views
Given a triangle $T$, to find the convex region $C$ for which $T$ is the smallest containing triangle
We add a bit to Given an n, which unit area planar convex region has the smallest maximal area inscribed n-gon? Given any triangle $T$, how does one find the convex region $C$ such that $C$ is the ...
- 7,221
3 votes
0 answers
130 views
Given an n, which unit area planar convex region has the smallest maximal area inscribed n-gon?
Basic version of the question: Consider a unit area planar convex region $C$ and its maximal area inscribed triangle $T(C)$. Which shape of unit area $C$ minimizes the area of its $T(C)$? General ...
- 7,221
5 votes
3 answers
602 views
Self-evident truths in Computational Geometry
I needed to use Computational Geometry result citations for my article. The article topic is Machine Learning. Some of citations I found, but for others it appears that they belong to so called "...
- 79
1 vote
1 answer
190 views
Forming the polygon of max area given edge lengths in random order
Given n real numbers with no one of them greater than the sum of the others, how does one form the polygon of max area with the n numbers as edge lengths? Does one try to form a cyclic polygon with ...
- 7,221
2 votes
0 answers
153 views
How bad is a centroidal Voronoi tessellation for disk covering?
The "disk covering problem" asks for the smallest positive number $r(n)$ so that $n$ disks of radius $r(n)$ can be arranged to cover a unit disk on the plane. Several centroidal Voronoi ...
2 votes
0 answers
112 views
Bijective voxel surface compression
Motivation It's straightforward to see that in any 4x4x4 voxel grid, if we represent voxels as being either solid (1) or empty (0), we can represent that grid as a 64-bit unsigned integer. Using the ...
3 votes
1 answer
279 views
The least area quadrilateral containing a set of points on the plane
How does one find the least area quadrilateral (allowed to be non-convex) that just contains a given set of n points on the plane? One could assume the points to be more than 4 in number and in ...
- 7,221
1 vote
0 answers
52 views
'Max (and min) Geodesic Poles' on surfaces of solids
Here we refer to the surface of a convex 3D solid as simply 'solid'. Let us define a max geodesic pole to be a point on a solid maximizing the average geodesic distance from it (measured along the ...
- 7,221
1 vote
0 answers
144 views
Construct an orthogonal simple polygon from a set of N mid–points
I am interested in the complexity of this problem: Input: Given N points on integer 2D grid (N is even) Question: Can we construct an orthogonal simple polygon from the set of N mid–points? Each mid–...
- 3,035
2 votes
1 answer
153 views
How to unfold a convex polyhedron minimizing the area of the convex hull of the 'unfolded planar embedding'
Earlier posts: How big a box can you wrap with a given polygon? Pairs of farthest points on surfaces of 3D convex solids Ref with 'unfolding' defined: Agarwal, Pankaj K., Boris Aronov, Joseph O'...
- 7,221
7 votes
1 answer
376 views
Given three skewforms on $\mathbb{C}^6$, is there always a common three-dimensional isotropic subspace?
Let $V = \mathbb{C}^6$ and let $\alpha_1, \alpha_2, \alpha_3 : V \times V \to \mathbb{C}$ be three alternating bilinear forms. Is there always a 3-dimensional subspace $U \le V$ such that $\alpha_i|U =...
- 11.4k
4 votes
1 answer
350 views
Algorithm to find the longest ‘surface geodesic’ on a convex polyhedron
We add a bit to Pairs of farthest points on surfaces of 3D convex solids Given a convex solid S. For a pair of points on its surface, call the length of the shortest path between them that lies ...
- 7,221
1 vote
0 answers
117 views
To partition a triangle into $n$ convex pieces with sum of number of sides over all pieces maximized
This post is a variant on To cut a triangle into $n$ $p$-sided polygonal regions. Question: Given a positive integer $n$, a triangular region is to be cut into $n$ convex pieces so that the sum over ...
- 7,221
0 votes
0 answers
97 views
Reflections of Voronoi diagrams
I wonder if something similar to the following fact is known, and I would greatly appreciate any references. Let $t_1, t_2, \ldots, t_N$ be unit vectors in $\mathbb{R}^n$. Let $S$ denote the unit ...
- 1
1 vote
0 answers
56 views
Computing all roots of a function with square-root terms
Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function $$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$ Can we find all the ...
- 11
0 votes
0 answers
77 views
Constructing a minimum-volume outer approximation polytope with fewer facets
I am tackling the following problem: Given a set of points $D \in \mathbb{R}^d$ and their convex hull, represented with $n$ facets, I want to construct a convex polytope $P$ with at most $m<n$ ...
- 101
1 vote
0 answers
109 views
On partitioning the surface of a convex solid into geodesically convex equal area regions
We refer to a subset S of the surface of a convex solid C as geodesically convex if the shortest path along the surface of C joining any two points in S lies entirely within S (and if there are more ...
- 7,221
1 vote
0 answers
27 views
Complexity of counting maximal points in query orthogonal rectangles
The problem stated in the title is the following: given an $n\times n$ binary matrix $M=\left(m_{rc}\right)$ report the number of $1$'s in a query rectangle $[i,j]\times[h,k]$ $1\le i\lt j\le n,\, 1\...
- 13.9k
1 vote
1 answer
412 views
Left and right halves of convex curve
Let $S$ be a set of $n$ points in the plane in general position (no 3 on a line), $n$ even. A halving line is a line through $2$ points of $S$ that partitions $S$ into 2 equal parts ($(n-2)/2$ points ...
- 6
1 vote
0 answers
50 views
Calculating an optimal scaling factor for Delaunay triangulations
consider a finite set $\mathcal{P}(x,y)=\lbrace(x_1,y_1),\dots,\,(x_n,y_n)\rbrace$ of points in the Euclidean plane and let $\mathrm{DT}(x,y)$ be the Delaunay triangulation of $\mathcal{P}(x,y)$ ...
- 13.9k
3 votes
1 answer
240 views
Why is the Vietoris–Rips complex $\operatorname{VR}(S, \epsilon)$ a subset of the Čech complex $\operatorname{Čech}(S, \epsilon\sqrt{2})$?
$\DeclareMathOperator\Cech{Čech}\DeclareMathOperator\VR{VR}$I am reading Fasy, Lecci, Rinaldo, Wasserman, Balakrishnan, and Singh - Confidence sets for persistence diagrams (see here for a version of ...
10 votes
0 answers
272 views
Placing triangles around a central triangle: Optimal Strategy?
This question has gone for a while without an answer on MSE (despite a bounty that came and went) so I am now cross-posting it here, on MO, in the hope that someone may have an idea about how to ...
- 8,096
3 votes
1 answer
519 views
Detecting a PL sphere and decompositions
Question 1. A PL $n$-sphere is a pure simplicial complex that is a triangulation of the $n$-sphere. I'm looking for a computer algorithm that gives a Yes/No answer to whether a given simplicial ...
- 923
1 vote
1 answer
141 views
Algorithm to find largest planar section of a convex polyhedral solid
We add a bit more on shadows and planar sections following On a pair of solids with both corresponding maximal planar sections and shadows having equal area . We consider only polyhedrons. Given a ...
- 7,221
1 vote
1 answer
185 views
An algorithm to arrange max number of copies of a polygon around and touching another polygon
A related post: To place copies of a planar convex region such that number of 'contacts' among them is maximized Basic question: Given two convex polygonal regions P and Q, to arrange the max ...
- 7,221
1 vote
0 answers
200 views
Explicit computation of Čech-cohomology of coherent sheaves on $\mathbb{P}^n_A$
$\newcommand{\proj}[1]{\operatorname{proj}(#1)} \newcommand{\PSP}{\mathbb{P}}$These days I noticed the following result of (constructive) commutative algebra, which I think is probably well known ...
- 748
5 votes
0 answers
528 views
Closest vertices of an AABB to a ray in n-dimensions
I came across this computational geometry problem and have not been able to find a satisfactory solution for it. A ray is known to originate from within an n-dimensional hypercube (AABB) in any ...
- 91
1 vote
1 answer
235 views
Inside-out dissections of solids -2
We record some general questions based on Inside-out dissections of solids Inside-out dissections of a cube Can every convex polyhedral solid be inside-out dissected to a congruent polyhedral solid?...
- 7,221
3 votes
0 answers
144 views
Practical way of computing bitangent lines of a quartic (using computers)
Are there known practical algorithms or methods to calculate the bitangent lines of a quartic defined by $f(u,v,t)=0$ in terms of the 15 coefficients? Theoretically you can set up $f(u,v,-au-bv)=(k_0u^...
- 101
1 vote
0 answers
122 views
Inside-out dissections of a cube
Ref: Inside-out polygonal dissections Inside-out dissections of solids Definitions: A polygon P has an inside-out dissection into another polygon P' if P′ is congruent to P, and the perimeter of P ...
- 7,221
5 votes
1 answer
340 views
Is the maximal packing density of identical circles in a circle always an algebraic number?
There is a lot of interest in the maximal density of equal circle packing in a circle. And I thought that knowing whether or not the solution is always algebraic or not would be useful. My original ...
- 53
1 vote
1 answer
179 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, ...
- 7,221
6 votes
2 answers
285 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 (...
- 7,221
0 votes
0 answers
56 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
1 vote
0 answers
120 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 ...
- 7,221
1 vote
0 answers
88 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
1 vote
1 answer
103 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 ...
- 7,221
1 vote
0 answers
133 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....
- 7,221
0 votes
0 answers
112 views
Comparing partitions of a given planar convex region into pieces with equal diameter 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 ...
- 7,221
1 vote
0 answers
130 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 ...
- 7,221
3 votes
0 answers
146 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 ...
