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
0answers
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
2answers
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
2answers
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
2answers
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
1answer
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
2answers
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
0answers
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
2answers
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
2answers
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
2answers
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
1answer
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
3answers
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
4answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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 ...
