# 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

0
votes

0
answers

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

1
vote

0
answers

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

0
votes

0
answers

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

3
votes

2
answers

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

3
votes

0
answers

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$, ...

1
vote

0
answers

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

3
votes

1
answer

163
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

95
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

54
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

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

16
votes

1
answer

525
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

57
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

158
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]}{\|...

2
votes

1
answer

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

5
votes

3
answers

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

1
vote

1
answer

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

3
votes

0
answers

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

2
votes

1
answer

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

0
votes

0
answers

25
views

### What is the most dense sample for which the Crust algorithm returns an incorrect polygonal reconstruction?

The Crust algorithm by Amenta, Bern, and Eppstein computes a polygonal reconstruction of a smooth curve $C$ without boundary from a discrete set of sample points $S$. It is known that if $S$ is an a $\...

-2
votes

1
answer

190
views

### Are there any non-elementary functions that are computable?

Does a function $\mathit{f}:\mathbb{R}→\mathbb{R}$ being non-elementary (not expressible as a combination of finitely many elementary operations), imply that it is not computable?
The particular case ...

5
votes

1
answer

240
views

### Counting points above lines

Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\...

5
votes

0
answers

156
views

### Computing sums with linear conditions quickly

Let $f:\{1,\dotsc,N\}\to \mathbb{C}$, $\beta:\{1,\dotsc,N\}\to [0,1]$ be given by tables (or, what is basically the same, assume their values can be computed in constant time). For $0\leq \gamma_0\leq ...

1
vote

0
answers

57
views

### Explicit form of boundary operators of topological cones

Let $\Omega$ be a regular, finite, $n$-dimensional CW complex with chain modules $\mathscr{C}_k$ and boundary operators $\partial_k$.
For many problems in computational geometry, a key operation is to ...

3
votes

1
answer

97
views

### Constrained morphing of polygons

This post continues 'Constrained morphing' of planar convex regions
If an $m$-gon $P_m$ is to be morphed (altered continuously) into an $n$-gon $P_n$ with same area and perimeter, can one ...

2
votes

1
answer

77
views

### 'Constrained morphing' of planar convex regions

Morphing may be defined as a continuous transition of one shape to another. This post is about modifying planar regions continuously from one form to another under some constraints.
Qn: If $C_1$ and $...

1
vote

0
answers

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

11
votes

1
answer

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

3
votes

0
answers

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

11
votes

2
answers

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

3
votes

1
answer

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

0
votes

0
answers

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

0
answers

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

6
votes

2
answers

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

0
votes

0
answers

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

0
answers

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

1
vote

0
answers

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

2
votes

0
answers

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

0
answers

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

2
votes

0
answers

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

2
votes

0
answers

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

11
votes

1
answer

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

1
vote

0
answers

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

1
vote

0
answers

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

1
vote

0
answers

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

2
votes

1
answer

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

0
votes

1
answer

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

2
votes

0
answers

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

1
vote

0
answers

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

3
votes

0
answers

207
views

### Explicit computations of finite covers of genus one curves with two points of ramification

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

1
vote

0
answers

51
views

### Are cells of 4-polytopes a convex polyhedron by definition?

I'm going by the Wikipedia definition for a 4-polytope.
Do by definition, cells of 4-polytopes have to be a convex polyhedra?
If not, then are there polyhedra with non-convex faces?
If yes, is it the ...