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.

Filter by
Sorted by
Tagged with
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 ...
Nandakumar R's user avatar
  • 4,577
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 ...
Nandakumar R's user avatar
  • 4,577
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:...
Nandakumar R's user avatar
  • 4,577
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 ...
TCiur's user avatar
  • 381
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$, ...
0xbadf00d's user avatar
  • 131
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 ...
Anthony Quas's user avatar
  • 22.2k
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 $...
giulio bullsaver's user avatar
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 ...
Pritam Majumder's user avatar
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 ...
Nandakumar R's user avatar
  • 4,577
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 ...
Mathews Boban's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Nandakumar R's user avatar
  • 4,577
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]}{\|...
Mathews Boban's user avatar
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 ...
Alec Jacobson's user avatar
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$. ...
Omega Tree's user avatar
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 ...
Nandakumar R's user avatar
  • 4,577
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 ...
Nandakumar R's user avatar
  • 4,577
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 ...
pyridoxal_trigeminus's user avatar
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 $\...
M Wright's user avatar
  • 403
-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 ...
mishmish's user avatar
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 $\...
H A Helfgott's user avatar
  • 18.6k
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 ...
H A Helfgott's user avatar
  • 18.6k
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 ...
Daniel Shapero's user avatar
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 ...
Nandakumar R's user avatar
  • 4,577
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 $...
Nandakumar R's user avatar
  • 4,577
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 (...
I.M.J. McInnis's user avatar
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 ...
Paul Taylor's user avatar
  • 7,445
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 ...
Ali's user avatar
  • 117
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 ...
Slava Rychkov's user avatar
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 ...
pyridoxal_trigeminus's user avatar
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 ...
Hugo Pfoertner's user avatar
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-...
Nandakumar R's user avatar
  • 4,577
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 ...
Nandakumar R's user avatar
  • 4,577
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 ...
Robin Lee's user avatar
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 ...
Melanka's user avatar
  • 549
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 ...
Nandakumar R's user avatar
  • 4,577
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 ...
Mohammad Al-Turkistany's user avatar
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 ...
Nandakumar R's user avatar
  • 4,577
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 ...
Robin Lee's user avatar
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 ...
Nandakumar R's user avatar
  • 4,577
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$. ...
Igor Pak's user avatar
  • 16.1k
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,...
Fran's user avatar
  • 11
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 ...
Scezory's user avatar
  • 11
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 ...
bcp's user avatar
  • 135
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, ...
Max Behling's user avatar
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 ...
ccriscitiello's user avatar
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 ...
nilsiism's user avatar
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 ...
DSM's user avatar
  • 1,156
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 ...
Lev Borisov's user avatar
  • 5,126
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 ...
Ron Michal's user avatar

1
2 3 4 5
9