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

339
questions

**2**

votes

**1**answer

62 views

### Existence of solutions of polynomials systems (and their “rough” shape) over $\mathbb{R}$ & friends with positive-dimensional ideals

This is a follow-up (but self-contained) question to my previous one. There I asked about state-of-the-art methods to solve multivariate polynomials systems over non-algebraically closed fields in ...

**0**

votes

**0**answers

73 views

### On some optimal containers of a set of points on the 2D plane

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find
the smallest semicircular region (semidisk) that contains the points
the smallest ...

**0**

votes

**0**answers

34 views

### Finite element method reference, from the perspective of the finite elements themselves

I found the finite element chapters in The Finite Element Method of Elliptic Problems especially enlightening and would like to learn more about the theory behind the base components of a general ...

**4**

votes

**1**answer

111 views

### $\varepsilon$-net of a $d$-dimensional unit ball formed by power set of $V = \{+1, 0 -1\}^d$

I have a set of $d$-dimensional vectors $V = \{+1, 0, -1\}^d $. Then $P(V)$ constitutes the power set of $V$. I now construct a set of unit vectors $V_{\mathrm{sum}}$ from the power set $P(V)$ such ...

**2**

votes

**1**answer

110 views

### Implementation of Koebe–Andreev–Thurston circle packing?

The circle packing theorem (Koebe–Andreev–Thurston theorem) claims for a planar graph, we can pack disjoint circles, such that: the circles correspond to vertices and the disks are tangent if the ...

**2**

votes

**1**answer

58 views

### Discrete curve-shortening flow – numerical implementation

I need to investigate the properties of open curves which evolve according to the standard curve-shortening flow (Wikipedia link), but with fixed extremes as boundaries (si it should converge to the ...

**0**

votes

**0**answers

25 views

### Restrictions on crossing edges in Delaunay triangulations

what can be said about crossing edges in Delaunay triangulations, i.e. about pairs of edges that constitute to the heaviest perfect matching int the $K_4$ induced by the quadruplet of adjacent ...

**0**

votes

**0**answers

13 views

### Defining planar geometric shape hulls via graph connectivity

A fundamental problem in Computational Geometry is to generalize convex hulls to simple polygons that partition a given finite set $\boldsymbol{P}$ into two sets $\boldsymbol{C}$ of corners and $\...

**0**

votes

**0**answers

21 views

### Bipartite Euclidean matching: Statistics of a random edge?

In a bipartite Euclidean matching, see e.g. this thesis (and the corresponding diagram below), two point processes, denoted $B$ and $S$, drawn from a Euclidean space $\mathbb{T}$ (a torus with flat ...

**1**

vote

**0**answers

30 views

### How do I find the portion of a cell/voxel lying within a defined surface?

We have a 3-dimensional grid of voxels (or cells), with individual voxels being of volume $dx\,dy\,dz$ where $dx=dy=dz=1$.
A cone-like surface is defined by some function, $z = f(x, y)$, which in ...

**1**

vote

**0**answers

33 views

### fast V representation update of polytope

Say that I have both the V and the H representation of a (possibly unbounded) polytope $P$. I want to append a some rows to the H representation, how can I quickly update the V representation to ...

**4**

votes

**2**answers

182 views

### Is there an upper bound on the number of points in point cloud for which we compute the persistent homology?

I am interested in the topic of persistent homology (topological data analysis). According to what I read, there is some roadblock in the analysis of "big data" using persistent homology as it is ...

**0**

votes

**0**answers

19 views

### VC Dimension of a range space of (X,ΔR) where (X,R) is of vc dimension d

I have a question:
Let (X , F) be a range space of bounded VC-dimension D.
Show that the range space (X , ΔF), where ΔF = {SΔS'
| S, S' ∈ F} (and Δ denotes the
symmetric set difference) has VC-...

**0**

votes

**1**answer

92 views

### IntersectInP bug of Macaulay2 [closed]

I am trying to use the intersectInP command in Macaulay2, inside package ReesAlgebra. However, I tried to follow the exact code in the user-guide, but it doesn't run in my Ubuntu app (of win 10). Can ...

**2**

votes

**0**answers

39 views

### grobner basis of an ideal dependent on some parameter

Suppose $I = \langle f_1, ... , f_l \rangle$ is an ideal generated by polynomials $f \in k[x_1,\dots,x_n]$, where $k$ is a field of rational functions in some parameters $s_1,\dots,s_m$.
What are the ...

**1**

vote

**0**answers

41 views

### finding a good term order for grobner basis

What are the tricks to pick a "good" monomial order to find a Grobner basis for a given ideal?
By good I mean one in which the final Grobner basis has a simple expression in terms of the ...

**5**

votes

**0**answers

52 views

### special classes of ideals (eg. toric) that admit faster Buchberger algorithm?

I have heard that toric ideals allow one to speed up the Buchberger algorithm considerably (see Grobner bases of toric ideals, Remark 2,3). My question is two-fold:
What are the precise complexity-...

**8**

votes

**0**answers

157 views

### Characteristic polynomial of an $8 \times 8$ symmetric matrix with indeterminate entries related to octonionic multiplication

I consider $1,i,j,k,l,m,n,o$ the standard basis of the (complexified if you like) octonions ($\mathbb{O}$ for the octonions).
Let $a = x_1.1 +\ldots + x_8.o$, $b = x_9.1+ \ldots + x_{16}.o$ and $c = ...

**1**

vote

**0**answers

22 views

### Complexity of tour-expansion heuristic for the planar Euclidean TSP

This is a followup question to this one: Computational Geometric Aspects of Greedy Tour Expansion.
Assume that the candidate point, whose insertion into current incurs the least tour-length increase, ...

**4**

votes

**2**answers

145 views

### Algorithm for reporting all triangles with unique interior point

What is known about the complexity of and/or practical algorithms for reporting all triplets of points from finite set of at least four points of which no three are collinear in the Euclidean plane, ...

**0**

votes

**1**answer

67 views

### Existence of element $(x_0,y)$ in a set of common zeros for all $(x_0,y)$ satisfying system of inequalities

Let $f_1,f_2,\cdots,f_n,g_1,g_2\cdots,g_m\in \mathbb{R}[x,y]$, then define the affine variety and semi-affine variety as follows:
$V(f_1,f_2,\cdots,f_n):=\{(x,y)\in\mathbb{C}^2: f_1(x,y)=f_2(x,y)=\...

**3**

votes

**0**answers

48 views

### Signed triangulations of simplicial polyhedra

Let $\partial S$ be the boundary of a compact polyhedron $S\subset\mathbb{R}^3$, assumed to be generic, in the sense that every face of $S$ is a triangle, and so that there are exactly two triangles ...

**1**

vote

**0**answers

61 views

### Is there a workable numerical method for determining the center of a circle through three points? [closed]

I'm a 73-year-old engineer struggling with numerically implementing a math problem.
I am working on a kinematic linkage project that generates motion paths (as long sequences of x,y coordinates) of ...

**3**

votes

**0**answers

108 views

### Lower bound on the intersection of $\ell_1$ $n$-balls

Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ in $\ell_1$ norm, with distance $d$ and radius $R$.
Is there a lower bound on the volume of the intersection between the two n-balls? (assuming the ...

**1**

vote

**0**answers

26 views

### Vertex enumeration for polytope with a sparse halfplane description?

Say I have a (bounded convex) polytope $P\subset\mathbb R^d$ with description $Ax\le b$, where $A$ is sparse in the sense that there are at most $k$ nonzero entries in each row or column, where $k$ is ...

**3**

votes

**1**answer

128 views

### Reference: Packing under translation is in NP

I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...

**1**

vote

**0**answers

47 views

### How does one translate from convex hull to a set of facets (inequalities)? [duplicate]

Suppose I have defined a convex set as the convex hull of a set of points. (I know that all these points are "extremal points" of the convex set.) I know want to translate this description of the ...

**2**

votes

**0**answers

63 views

### Software recommendation request: deciding whether a system of polynomial equations is solvable by radicals

The following system of equations comes from a very simple geometric figure I have to deal with a lot at work. Here $r_0,r_1,r_2$ and $L$ are known parameters, and the $x_i$s are the coordinates I'm ...

**3**

votes

**1**answer

162 views

### What is the form of the $(v_0,v_1)$-pizza curve?

Assume that there are two (competing) pizza houses situated at the points $0$ and $1$ on the complex plane. These pizza houses can deliver pizza to points of the plane with the largest velocities $v_0$...

**4**

votes

**2**answers

409 views

### Convex hull in a discrete space [closed]

I know some algorithms which compute the convex hull in a continuous space.
Are there efficient algorithms to compute it in a discrete domain?
For example in 3D discrete space, given the blue points, ...

**1**

vote

**1**answer

188 views

### Partitioning polygons into acute isosceles triangles

Question: Given an $N$-vertex polygon (not necessarily convex). It is to be cut into the least number of acute isosceles triangles.
Remarks:
Based on this MathSE discussion, one can think of a ...

**7**

votes

**1**answer

396 views

### To minimize the Hausdorff distance between convex polygonal regions

Definition: The Hausdorff distance is the greatest of all the distances from a point in one set to the closest point in the other set.
Question: Given two convex polygonal regions P1 and P2 on the ...

**4**

votes

**0**answers

70 views

### Problem to efficiently compute the Volume of $d$ anchored 4D cuboids

An easy still unsolved special case of Klee's measure problem with applications in multiple objective optimization is described in the following.
Let $[\vec a_1,\vec b_1],\dots,[\vec a_n,\vec b_n]$ ...

**6**

votes

**1**answer

113 views

### Minimizing the number of segments in drawings of planar graphs

Every planar graph has at most $3n-6$ edges, where $n$ is the number of vertices. Moreover, every planar graph can be drawn with straight-line edges in the plane, without crossings. For example, for ...

**2**

votes

**1**answer

83 views

### Given a set of $n$ points in $[0,1)^d$, how do I partition the space into hyperrectangles such that each hyperrectangle contains exactly one point?

I'm new to this forum so I apologize if my question is ill-posed or too general. I have the following problem. Given a set of $n$ points in the unit hypercube, $[0,1)^d$, how can I partition the unit ...

**5**

votes

**3**answers

126 views

### Fast computation of a ball with radius r with largest number of input points

We are given a set S of n points equipped with some metric and an integer $r>0$. We define $B(x,r) \subseteq S$ (the ball with radius r centered in x) to be the set of points in S within distance r ...

**5**

votes

**1**answer

257 views

### On covering convex 2D regions with rectangles

Given a convex 2D region $C$ and a positive integer $N$. We need to cover $C$ with $N$ rectangles such that the sum of the areas of the $N$ rectangles is the least – no further constraints on the ...

**1**

vote

**1**answer

89 views

### Estimating volume of a simple object

Volume computation is $\#P$ hard.
Take the $[0,1]^n$ polytope.
Slice it by an half space inequality with $poly(n)$ bit rational coefficients into two unequal halves.
Volume of bigger section is $\...

**2**

votes

**0**answers

42 views

### Complexity of existence of simple polygonalization with prescribed area?

This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...

**6**

votes

**0**answers

194 views

### Complexity of scissors congruence?

Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with ...

**2**

votes

**1**answer

100 views

### Intersection of sphere with triangle containing moving vertices

First off, apologies if I cannot properly articulate my question in the most formal way. However, I believe my question should be simple enough to grasp anyhow.
In $\mathbb{R}^3$, I would like to ...

**1**

vote

**0**answers

55 views

### Projection of a polytope along 4 orthogonal axes

Consider the following problem:
Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...

**16**

votes

**2**answers

264 views

### Finding a plane numerically

Suppose I have three large finite sets $\{x_i\}$, $\{y_i\}$ and $\{z_i\}$;
they are obtained by measuring coordinates of a collection of vectors in $\mathbb{R}^3$, but I do not know which triples ...

**3**

votes

**1**answer

258 views

### How to find the vertices of the set $\{v_i\in \mathbb{R}:a_1\ge v_1\ge v_2\ge \cdots\ge v_n\ge 0,\ q_2\le \sum_{i=1}^n p_iv_i\le q_1\}$

I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, $q_2\le \sum_{i=1}^n p_iv_i\le q_1$, with $\{p_i\}_{i=1}^n,\ q_1,q_2$ positive reals, and only one bound for the coordinates: $v_1\...

**1**

vote

**0**answers

44 views

### Efficient scissors congruence between efficiently describable convex polytopes and simplex?

Is there a convex polytope in $\mathbb R^n$ describable by only $O(poly(\log n))$ half-plane inequalities with positive volume (so at least $n+1$ vertices) such that the standard simplex has a ...

**1**

vote

**0**answers

35 views

### Covering a simplex efficiently by efficiently describable polytopes?

Take a standard simplex or cube in $\mathbb R^n$.
Is there a way to cover it with $O(poly(\log n))$ convex polytopes each describable by only $O(poly(\log n))$ half-plane inequalities?
If not what ...

**1**

vote

**0**answers

59 views

### Polytopes that can be efficiently described and efficiently covered by cubes or simplices?

Is there a bounded convex polytope $\mathcal P\subseteq\mathbb R^n$ with $m$ vertices, whose vertex vectors span $\mathbb R^n$ (so $m$ is $\Omega(n)$) and just $O(poly(\log n))$ half-plane ...

**2**

votes

**1**answer

122 views

### Build reversed No-Fit-Polygon

I need some robust algorithm to optimally fit one non-convex polygon into another. The destination one can contain holes.
Recently I found scholarly articles on this subject:
One of them describes ...

**2**

votes

**1**answer

127 views

### Algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane

I am trying to find an algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane, with a total of $n$ vertices. Let $h$ denote the number of vertices on ...

**2**

votes

**1**answer

86 views

### A questions concerning Laguerre/Voronoi tessellations

Fix $n>1$ distinguished points $x_1,\ldots, x_n\in \mathbb R^d$, the Voronoi tessellations are the subsets $V_1,\ldots V_n\subset\mathbb R^d$ defined by
$$V_k~~ := ~~ \big\{x\in\mathbb R^d:\quad |...