As of May 31, 2023, we have updated our Code of Conduct.

# 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.

449 questions
Filter by
Sorted by
Tagged with
34 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 ...
• 4,577
1 vote
53 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 ...
• 4,577
18 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:...
• 4,577
192 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 ...
• 381
71 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$, ...
• 131
1 vote
61 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 ...
• 22.2k
163 views

43 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 ...
506 views

### If a polyhedron in $\mathbb{R}^3$ has local intersections, does it also have more global intersections?

Consider a simplicial complex $K$. A piecewise linear map $f: K \to \mathbb{R}^n$ is an almost-embedding if $f(\sigma) \cap f(\tau) = \emptyset$ for any two disjoint simplices $\sigma,\tau$ in $K$. ...
• 141
1 vote
106 views

### Smallest trapeziums containing a given convex n-gon

Question: Given a planar convex $n$-gon $C$, to find the smallest area / smallest perimeter trapezium (trapezoid) - a convex quadrilateral with at least one pair of mutually parallel edges - that ...
• 4,577
62 views

### Cutting triangles into triangles with equal longest side

This post elaborates on a specific instance of Cutting convex polygons into triangles of same diameter . Question: For any integer n, can any triangle be cut into n non-degenerate triangles all of ...
• 4,577
107 views

### Do there exist smaller simplicial models of barycentric subdivisions?

Let $S$ be a simplicial complex and let $Bary(S)$ denote its barycentric subdivision. Of course, the geometric realizations of $S$ and $Bary(S)$ are homeomorphic. However, one issue that arises in ...
25 views

• 18.6k
156 views

• 4,577
1 vote
31 views

### Computational hardness of a discrete generalized rectangle packing problem

I have a decision problem that is clearly in NP, but I cannot seem to prove that it is in P, nor can I prove its NP-hardness. I attribute this more to my inexperience than to the problem's difficulty (...
324 views

### Tarski-Seidenberg for strict inequalities and bounded quantification

This theorem says that quantifiers over real variables can be eliminated from classical first order formulae built from equations and inequalities between polynomials with rational coefficients, ie in ...
• 7,445
104 views

### Hemisphere containing the maximum number of points scattered on a sphere

Consider a set of points $x_1, \ldots,x_n$ on $\mathbb{S}^{k-1}$ (the unit sphere in $\mathbb{R}^k$). The goal is finding the hemisphere which contains the maximum number of $x_i$'s. Basically, we ...
• 117
575 views

### A quadratic $O(N)$ invariant equation for 4-index tensors

Consider an $O(N)$ invariant quadratic equation $$T_{ijkl}= T_{ijmn}T_{klmn}+ T_{ikmn}T_{jlmn}+ T_{ilmn}T_{jkmn},$$ where $T_{ijkl}$ is a real, totally symmetric 4-tensor, and the indices run from 1 ...
94 views

### Results in computational geometry utilizing doubling dimension of a metric space

According to Wikipedia, However, many results from classical harmonic analysis and computational geometry extend to the setting of metric spaces with doubling measures. My question is: what are some ...
81 views

### Upper bound on the diameter of a convex lattice n-gon with a given area

Given the area $A$ of ​​a strictly convex polygon with $n$ vertices with integer Cartesian coordinates, there are usually several non-equivalent polygons. The relationship between the area, the number ...
1 vote
44 views

### Triangulation of polygons with all triangles having a common angle

Following Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles, we record another triangulation question. Question: Given an n-vertex polygonal region ("n-...
• 4,577
188 views

### Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles

Definition: Let us refer to obtuse triangles with the largest angle strictly above a given cutoff value as 'strongly obtuse' - the definition is parametrized by the cutoff value. Likewise, strongly ...
• 4,577
69 views

### Boolean operation on n dimensional polyhedron

A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$. Given a set of polyhedra in $R^n$, $P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...
1 vote
68 views

### Translate of a geodesic that goes through a fixed point on $\mathbb{H}$

Consider the complex upper half plane $\mathbb{H}$ with the hyperbolic geometry. Fix a point $z \in \mathbb{H}$ and also a geodesic $c$. I want to find a hyperbolic translation $\gamma c$ passes that ...
• 549
1 vote
41 views

### Dissection of polygons that preserve boundaries

Ref: Inside-out polygonal dissections Further queries on inside-out polygonal dissections Question: Consider any two polygons P1 and P2 with equal area and equal perimeter. Is it always possible to ...
• 4,577
150 views

### Is orthogonal polygon with crossings count NP-complete?

The are several NP-complete problems related to the construction of orthogonal simple polygons. Rapport showed that it is NP-complete to decide the existence of orthogonal simple polygon that passes ...
1 vote
29 views

### Partitioning convex n-gons into least number of equal area convex quadrilaterals

This post adds a bit to Partitioning convex polygons into quadrilaterals of equal area and perimeter Question: How does one achieve the partition of any given convex n-gon into the least number of ...
• 4,577
56 views

### The fastest way to sample points on an implicit manifold, or projecting points on a manifold

Given a compact manifold $M$ in $R^n$, $M = f(x)$, f(x) is infinitely differentiable. $x$ $\in$ $R^n$, I want to find a bunch of samples on the manifold. Currently, I'm setting up an SQP optimization ...
80 views

### Ellipse of least perimeter that contains a given triangle

This post is related to Smallest 3-ellipses that contain triangles and tries to clarify a basic issue. Question: Given a general triangle T, How does one find and characterize the ellipse of least ...
• 4,577
317 views

### Complexity of counting regions in hyperplane arrangements

Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$. ...
• 16.1k
1 vote
36 views

### What are some other methods for partitioning an n-dimensional space based on a set of points in that space?

So this is a very general question, but I'm curious if there are any other methods for partitioning an n-dimensional space based on the location of a set of points, either randomly chosen or specified,...
• 11
1 vote
32 views

### Efficient solution to linear matrix equations

A general form for a linear matrix equation can be written as $$AX + XB + \sum C_iXD_i$$ If $C_i$ and $D_i$ are all 0, then this simplifies into a well known and studied matrix equation that has an ...
• 11
1 vote
89 views

### Computer algebra tools for finding real dimension of an algebraic variety

I have a system of polynomial equations with the unknowns being real numbers. The set of solutions is infinite. What software can I use to compute the real dimension of the solution set? The CAD-based ...
• 135
71 views

### Determining if a polygon is convex using relations on orientation of each ordered triple of points

I am reading a paper by Szekeres and Peters on computing the 17-point case of the Erdős–Szekeres conjecture. The conjecture states that the minimum number of points in the plane (in general position, ...
• 123
116 views

### Reference request: How to construct a diffeomorphism between point clouds

I'm interested in the following question: Given two sets $S = \{x_1, ..., x_N\}$ and $T = \{y_1, ..., y_N\}$ each consisting of $N$ distinct points in $\mathbb{R}^n$, how can we construct a ...
44 views

### Cylinder orientation representation

I'm trying to find an efficient computation and representation for the following problem. Given a cylinder with height $h$ and radius $r$ with a given position $\mathbf{x} = [x, y, z]$ and $N$ number ...
• 21
1 vote
33 views

### Fermat point amidst polygonal obstacles

Consider $k$ distinct points in 2D-plane with $n$ convex polygonal obstacles. Is there a poly-time algorithm (poly in $k$ and the total number of obstacle vertices) to find a point outside of all ...
• 1,156
I have an explicit genus one curve $E$ with two points $p_1$ and $p_2$ on it and am looking for an explicit degree seven cover $X\to E$ with ramification precisely over $p_i$, with a single preimage ...