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

**3**

votes

**0**answers

48 views

### Biggest Cartesian Product Included in a Real Plane Curve

Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as ...

**4**

votes

**2**answers

82 views

### Complexity of Random Delaunay Triangulation in 3D

My question:
Is the number of cells in a three-dimensional Poisson-Delaunay triangulation with $n$ vertices $\mathcal O(n)$ with probability one?
which is equivalent to the question
Is the ...

**4**

votes

**1**answer

166 views

### Generalizations of the “Curious Tiger” Polygon

I actually don't know, whether the polygon I describe here already has name, but let me explain the problem, that is solved by the polygon, with a little story:
Imagine a flat terrain with bushes ...

**2**

votes

**0**answers

46 views

### Efficient algorithm to prove that a polynomial ideal contains 1

I have the following problem:
Suppose to have an ideal $I\triangleleft k[x_1,...,x_n]$ defined by generators. There exists an efficient algorithm (perhaps more efficient than calculating the Groebner ...

**1**

vote

**1**answer

73 views

### computing the boundary of a union of polytopes

Let $P_1,\dots ,P_m\subset \mathbb{R}^n$ be $m<\infty$ convex polytopes in $\mathbb{R}^n$, and $U:=\bigcup_{j} P_j$ their set-theoretic union. What algorithms are known for computing the boundary $\...

**4**

votes

**2**answers

148 views

### largest diameter of intersection of two balls

Two closed balls with a common radius are positioned so that the centre of either ball is on the boundary of the other.
I am interested in the extremal diameter of their intersection, in an arbitrary ...

**6**

votes

**0**answers

103 views

### Does the problem of recognizing 3DORG-graphs have polynomial complexity?

A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...

**3**

votes

**0**answers

73 views

### Algorithm to compute the Voronoi diagram of points, line segments and triangles in $\mathbb{R}^3$

Is there a known algorithm to compute the (generalized) Voronoi diagram of a set of points, line segments and triangles in $\mathbb{R}^3$? If yes, are there any available implementations?
I know that ...

**3**

votes

**1**answer

81 views

### On using a 3D convex hull to compute a 2D Voronoi diagram

I am working in a computing environment that has the facility to compute general nD convex hulls and not much else in the way of computational geometry. The routine, given a set of points, gives the ...

**2**

votes

**1**answer

49 views

### Compute the hull of nonnegative linear combinations of a finite set, and the extreme points of the intersection of two polyhedra

Let $\mathbb{R}^d$ be $d$-dimensional Euclidean space
Let $\Delta=\{x\in\mathbb{R}^d_+:\sum_{i=1}^dx^i\leq1\}$ ($x^i$ is the i-th coordinate of $x$)
(Equivalently, $\Delta$ is the convex hull of $\{(0,...

**4**

votes

**2**answers

246 views

### Fast projection onto a subspace

Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...

**3**

votes

**2**answers

122 views

### Cone-Torus intersection in 3D

Problem. I have a solid torus and a solid cone in $\mathbb R^3$ and need an efficient algorithm that determines if they intersect or not.
The center of the torus is at a given position $\mathbf p \in ...

**5**

votes

**2**answers

129 views

### Checking a Guarding for the Art Gallery Problem

In the Art Gallery Problem, we have given
a polygon $P$ on $n$ vertices and a number $k$ and we
want to know if there exists $k$ guards
such that every point inside the polygon
is seen by at least ...

**3**

votes

**1**answer

54 views

### How to value the extent of separation or mixing of point sets in plane?

As the image presented below, the reddish point set is totally separated from the blueish one and the greenish one, while the blueish point set is quite mixed with the greenish one.
A number of ...

**2**

votes

**2**answers

94 views

### Monotonicity for the side lengths of stars inscribed in regular polygons

Fix integers $l\ge 1$ and $n \ge 3$, and let $P_n$ denote the boundary of the regular $n$-sided polygon in the plane. We define a $(2l+1)$-pointed equilateral star to be a cyclically ordered list of ...

**0**

votes

**0**answers

59 views

### Applying a piecewise linear function to vertices of a polytope while remaining in facet representation

Let $P \subseteq \mathbb{R}^d$ be a polytope with vertices $V$, and let $f : \mathbb{R}^d \to \mathbb{R}$ be a function. Let $P' \subseteq \mathbb{R}^{d+1}$ be the polytope with vertices $\{(v, f(v)) \...

**2**

votes

**2**answers

104 views

### Discrete approximation of Minkshisundaram-Pleijel zeta function?

I'm looking for some references on the following situation:
$S$ is a Riemannian surface, and $G_n$ is a sequence of metric subgraphs embedded on $S$. Let $\zeta_n$ be the zeta function of the ...

**4**

votes

**2**answers

174 views

### Fitting one Polygon in another

I have two Polygons A and B and I want to find the position, rotation and scale of B, so it fits into A and has the maximum Area possible. Also both can be concave.
I did some research but couldn't ...

**3**

votes

**1**answer

87 views

### Shortest Manhattan-norm paths among disjoint rectangles

I am looking for the fastest possible algorithm for solving the following problem: I am given a collection of disjoint axis-aligned rectangles in the plane, and I need to pre-process these rectangles ...

**4**

votes

**2**answers

80 views

### How many dihedral angles need to be specified to uniquely specify a triangulated polyhedron?

Suppose you are given a simplicial complex $K$ homeomorphic to the sphere and for each each edge of the complex a label specifying a length of that edge (this gives us a polyhedral metric on $K$). In ...

**2**

votes

**1**answer

180 views

### Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?

Sorry the title may be unclear. I do not know how to give it a good title.....
Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....

**5**

votes

**1**answer

109 views

### Minimum euclidean spanning tree in n dimensional space

I need to compute the minimum euclidean spanning tree in $R^d$ and do it with some algorithm that can do it with complexity near to $\Omega(nlogn)$ where $n$ is the size of the point set.
Right now I'...

**2**

votes

**0**answers

100 views

### How to compute explicit equations for the Jacobian of a variety over a field [duplicate]

Suppose we start with a projective curve $X$ over a field $K$, given as a closed subvariety of $\mathbb P^n_K$ by some explicit list of equations. I would like to find an explicit representation of ...

**4**

votes

**0**answers

86 views

### Cylindrical Decomposition vs Morse decomposition

Suppose I have a polynomial Morse function $f: \mathbb{R}^n \to \mathbb{R}$. Consider the ideal $I(\nabla f)$ generated by the partial derivatives $\partial_i f$, and assume that the real zero-set of ...

**1**

vote

**0**answers

44 views

### The upper bound of the number of points of a convex hull formed by external co-tangents of circles

Consider the following problem: Given a rope to surround some circles, and minimize the length of the rope.
In order to solve the problem, we shall calculate all external co-tangents of these circles, ...

**1**

vote

**1**answer

107 views

### Computational Geometric Aspects of Greedy Tour Expansion

Has the following problem already been investigated from the Computational Geometry point of view and what are the results regarding worst case complexity?
Given
a finite set $\mathcal{P}...

**6**

votes

**1**answer

366 views

### How many triangulations of a regular octahedron are there, without introducing new vertices?

It is easy to find three triangulations, each consisting of four tetrahedra. Are there more?

**0**

votes

**0**answers

56 views

### Minimum-cost vertex transformations to achieve a planar graph embedding

Consider an undirected planar graph $G = (V,E)$ (not necessarily simply connected) whose current embedding in the plane has edge intersections.
Consider algorithms in which vertexes $v_i$ can be ...

**1**

vote

**0**answers

85 views

### Geometry of a $(d-1)$-dimensional lattice

Let $\mathbf u\in\mathbb Z^d$ be a primitive vector (i.e. $\gcd(u_i)=1$) and let $\Pi_{\mathbf u^\perp}$ be the orthogonal projection perpendicular to $\mathbf u$. I want to understand the geometry of ...

**1**

vote

**0**answers

57 views

### What kind of transformations can I do on a 2D Voronoi diagram and have it remain valid? [closed]

I'm a programmer trying to implement a graphical effect using 2D Voronoi diagrams, and I'm wondering what kind of basic geometric transformations I can apply to it while having it still remain a valid ...

**1**

vote

**0**answers

41 views

### Congruency check for set of points in 3D using inertia tensor

You're given two set of points $A, B\subset \mathbb R^3:|A|=|B|=n$. You have to check if those sets are congruent, i.e. there exist some mapping $\sigma : A \to B$ and combination of translation and ...

**4**

votes

**1**answer

82 views

### Points on lines with prescribed distances to each other

Given three lines $l_a, l_b, l_c$ in $\mathbb {R}^3$ and three positive numbers $a, b, c>0$ I would like to find points $A, B, C$ on $l_a, l_b, l_c$ respectively, such that the side lengths of ...

**1**

vote

**2**answers

205 views

### Convergence of an iterated sequence

Let $K=[0,1]^2$ be a square and $p\in (0,1)$ be a fixed number. We define a map $F: K^2\to K^2$ as follows.
For $(x_1,y_1), (x_2,y_2)\in K$, it follows by a straightforward computation that there ...

**3**

votes

**1**answer

61 views

### How to cover n sites with the smallest number of fixed radius balls?

Given $n$ "data points" in $d$ (Euclidean) space
$$\mathbf{x}_j \in \mathbb{R}^d, \text{ for } j \in \{1,\dots,n\}$$
how does one find the smallest integer $m$ such that there exists $m$ "centre ...

**0**

votes

**1**answer

45 views

### Calculating a Measure of the Geometric Complexity of Planar Closed Polylines

Let $\lbrace p_1,\ \dots,\ p_n\rbrace$ be a set of points in the Euclidean plane and let $T_0 :=\left(p_1,\ \dots,\ p_n,p_1\right)$ be a Hamilton cycle through the set of points.
Question:
...

**5**

votes

**2**answers

202 views

### Convex caps with prescribed edges

Let $P$ be a convex polygon in the plane $R^2=R^2\times \{0\}$, and $E$ be the edge graph of some subdivision of $P$ into convex polygons, which is $3$-connected. Does there exist a convex polyhedral ...

**1**

vote

**0**answers

62 views

### First Betti number of a Reeb graph is not greater than that of the space?

(I have asked this question at math stackexchange, it was upvoted but got no answers; maybe you can help.)
It is well-known that $\beta_1(R(f))\le\beta_1(X)$, where $\beta_1$ is the first Betti ...

**4**

votes

**1**answer

147 views

### Volume of a finite union of overlapping balls?

Suppose I have finite list of $n$ 3-dimensional balls, specifying their positions and radii. The balls can have non-empty intersections.
Is there an algorithm to compute the volume of the region ...

**2**

votes

**2**answers

210 views

### Computer algebra for calculating curvature when the tensor metric is very big

Is there a computer algebra method to compute the curvature of a Riemannian metric on the plane when the metric tensor has long entries $E,F,G$
The computation by hand is very ...

**1**

vote

**1**answer

48 views

### Generating Convex Polygonal Neighborhoods from Triangulations of Discrete Pointsets

The wellknown Delaunay Triangulation $DT$ has as a straight line dual the also wellknown Voronoi Diagram $VD$.
Both are most commonly defined in the Euclidean plane and are primarily beneficial for ...

**27**

votes

**3**answers

3k views

### Can squares of side 1/2, 1/3, 1/4, … be packed into three quarters of a unit square?

My question is prompted by this illustration from Eugenia Cheng’s book Beyond Infinity, where it appears in reference to the Basel problem.
Is it known whether the infinite set of squares of side $\...

**6**

votes

**4**answers

374 views

### A quick algorithm for calculating the $\ell_1$-distance between two finite sets on the real line?

For two non-empty finite sets $A,B$ in the real line define the $\ell_1$-distance $d_1(A,B)$ between $A$ and $B$ as the smallest Lebesgue measure of a closed subset $\Gamma\subset \mathbb R$ such that ...

**9**

votes

**0**answers

348 views

### A new $\ell_p$-metric on the hyperspace of finite sets?

Let $(X,d)$ be a metric space and $Fin(X)$ be the family of all non-empty finite subsets of $X$. For every $n\in\mathbb N$ the elements of the power $X^n$ are thought as functions $f:n\to X$ where $n:=...

**3**

votes

**1**answer

362 views

### Intersections of quadratic planes as elliptic curves

An elliptic curve defined over a field $k$ is a smooth projective curve of genus $1$, plus a $k$-rational point. Every elliptic curve can be written in a Weierstrass form, i.e. as a plane cubic curve ...

**2**

votes

**1**answer

49 views

### Upper Envelope of Multidimensional Piecewise-Quadratic Functions

I am trying to find the upper envelope to a set of piecewise-quadratic functions. The problem is easy enough to solve in the 1-dimensional case, as it amounts to finding and pruning the intersections ...

**1**

vote

**1**answer

120 views

### Omitting constraints of polynomial system

Let $n_1, n_2 \geq 1$ be known integer constants.
Suppose that we have the following system of $n$ polynomial inequalities
for which we know that there exists a feasible solution $(p_1, p_2) \in (0,1)...

**5**

votes

**0**answers

265 views

### Can this set of equations be solved explicitly for algebraic curves?

In my recent work I stumbled upon a set of two equations. I'm interested in solving by eliminating auxiliary variable "$z$" and getting algebraic curve in terms of $x$ and $y$ given by the zero locus ...

**4**

votes

**0**answers

197 views

### Reach of manifold vs. $C^k$-manifold

The reach $\tau_M$ of a manifold $M$ is the largest number such that any point at distance less than $\tau_M$ from $M$ has a unique nearest point on $M$.
This concept seems quite related to the local ...

**0**

votes

**1**answer

63 views

### algorithms and tools available for a particular polytope computation

Let me define each half space i as:
$${H_i}:{c_i}{\bf{x}} \le {b_i}$$
The intersection of all such ${H_i}$ gives a polyhedron (bounded or not). Suppose I am interested in if ${H_i}$ is active (...

**7**

votes

**1**answer

236 views

### Does generic projection into $\mathbb{R}^3$ preserve real-algebraic-curve-ness?

I'm interested in the topological properties of certain real algebraic curves in high-dimensional spaces. I want to visualize these curves (say, like this), and so I'm pursuing dimensionality ...