Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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