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.

Filter by
Sorted by
Tagged with
4 votes
1 answer
76 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 (...
Nandakumar R's user avatar
  • 5,451
0 votes
0 answers
24 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 ...
n1ps's user avatar
  • 1
0 votes
0 answers
43 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 ...
Nandakumar R's user avatar
  • 5,451
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 ...
GRquanti's user avatar
  • 111
0 votes
0 answers
58 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 ...
Ronald J. Zallman's user avatar
1 vote
1 answer
56 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 ...
Nandakumar R's user avatar
  • 5,451
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....
Nandakumar R's user avatar
  • 5,451
0 votes
0 answers
58 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 ...
Nandakumar R's user avatar
  • 5,451
1 vote
0 answers
74 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 ...
Nandakumar R's user avatar
  • 5,451
1 vote
0 answers
47 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 ...
pyridoxal_trigeminus's user avatar
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 ...
Nandakumar R's user avatar
  • 5,451
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 ...
Nandakumar R's user avatar
  • 5,451
0 votes
1 answer
54 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 ...
pyridoxal_trigeminus's user avatar
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 ...
Nandakumar R's user avatar
  • 5,451
2 votes
1 answer
249 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 ...
Pène Papin's user avatar
2 votes
0 answers
62 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 ...
Florin Andrei's user avatar
0 votes
0 answers
20 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 ...
Nandakumar R's user avatar
  • 5,451
0 votes
0 answers
45 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 (...
Nandakumar R's user avatar
  • 5,451
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 ...
HeyoItsMateo's user avatar
4 votes
2 answers
189 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 ...
catmousedog's user avatar
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 ...
Nandakumar R's user avatar
  • 5,451
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 ...
Nandakumar R's user avatar
  • 5,451
3 votes
0 answers
134 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 ...
PeterCrouch's user avatar
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 ...
Command Master's user avatar
2 votes
0 answers
91 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 ...
Jake Lai's user avatar
3 votes
1 answer
126 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 ...
mrburch's user avatar
  • 155
0 votes
0 answers
42 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....
BabaUtah's user avatar
0 votes
1 answer
48 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 ...
Nandakumar R's user avatar
  • 5,451
0 votes
0 answers
86 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 ...
Nandakumar R's user avatar
  • 5,451
6 votes
1 answer
341 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, ...
Taras Banakh's user avatar
  • 40.8k
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/...
Thibault Poiret's user avatar
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 ...
Nandakumar R's user avatar
  • 5,451
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 ...
Nandakumar R's user avatar
  • 5,451
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 ...
Nandakumar R's user avatar
  • 5,451
1 vote
2 answers
107 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 ...
Nandakumar R's user avatar
  • 5,451
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/...
Nandakumar R's user avatar
  • 5,451
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 ...
Nandakumar R's user avatar
  • 5,451
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 ...
Nandakumar R's user avatar
  • 5,451
0 votes
0 answers
22 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. Question:...
Nandakumar R's user avatar
  • 5,451
3 votes
2 answers
218 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 ...
TCiur's user avatar
  • 469
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$, ...
0xbadf00d's user avatar
  • 161
1 vote
0 answers
77 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 ...
Anthony Quas's user avatar
  • 22.5k
3 votes
1 answer
221 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 $...
giulio bullsaver's user avatar
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 ...
Pritam Majumder's user avatar
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 ...
Nandakumar R's user avatar
  • 5,451
0 votes
1 answer
107 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 ...
Mathews Boban's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Nandakumar R's user avatar
  • 5,451
2 votes
1 answer
184 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]}{\|...
Mathews Boban's user avatar
2 votes
1 answer
65 views

Example of worst case distributions for 4D convex hull

My understanding is that convex hull of n points in 4D could have O(n²) edges in the worst case. Source: https://sites.cs.ucsb.edu/~suri/cs235/ConvexHull.pdf This same source writes In 4D, there are ...
Alec Jacobson's user avatar

1
2 3 4 5
10