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
4 votes
2 answers
340 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 ...
Dahn's user avatar
  • 141
5 votes
1 answer
226 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 of ...
Manfred Weis's user avatar
  • 12.6k
2 votes
0 answers
61 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 ...
DDT's user avatar
  • 297
1 vote
1 answer
451 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 $\...
Dima Pasechnik's user avatar
4 votes
2 answers
408 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 ...
András Salamon's user avatar
7 votes
0 answers
120 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 ...
Lviv Scottish Book's user avatar
7 votes
3 answers
2k 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 ...
Leonardo Sacht's user avatar
3 votes
1 answer
436 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 ...
richard aspeto's user avatar
2 votes
1 answer
64 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,...
Yi-Hsuan Lin's user avatar
4 votes
2 answers
671 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{...
Penelope Benenati's user avatar
3 votes
2 answers
363 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 ...
user3749105's user avatar
5 votes
2 answers
396 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 ...
Till's user avatar
  • 469
3 votes
1 answer
93 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 ...
rube wang's user avatar
  • 143
2 votes
2 answers
123 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 ...
Adam Quinn Jaffe's user avatar
2 votes
2 answers
170 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 ...
Elle Najt's user avatar
  • 1,432
4 votes
2 answers
765 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 ...
Melodix's user avatar
  • 41
3 votes
1 answer
116 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 ...
Chuck Newton's user avatar
4 votes
2 answers
306 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 ...
John's user avatar
  • 185
2 votes
1 answer
344 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$....
Yi-Hsuan Lin's user avatar
5 votes
1 answer
413 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'...
Kevin's user avatar
  • 53
2 votes
0 answers
110 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 ...
Marc's user avatar
  • 374
4 votes
0 answers
119 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 ...
Simon Segert's user avatar
1 vote
0 answers
111 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, ...
zbh2047's user avatar
  • 601
1 vote
1 answer
127 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}...
Manfred Weis's user avatar
  • 12.6k
6 votes
1 answer
492 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?
John Kieffer's user avatar
0 votes
0 answers
76 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 ...
David G. Stork's user avatar
1 vote
0 answers
97 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 ...
Anthony Quas's user avatar
  • 22.5k
1 vote
0 answers
68 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 ...
Oskar's user avatar
  • 111
1 vote
0 answers
63 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 ...
Oleksandr  Kulkov's user avatar
4 votes
1 answer
88 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 ...
user35593's user avatar
  • 2,286
1 vote
2 answers
259 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 ...
user111097's user avatar
3 votes
1 answer
185 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 ...
Alec Jacobson's user avatar
0 votes
1 answer
66 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: ...
Manfred Weis's user avatar
  • 12.6k
5 votes
2 answers
290 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 ...
Mohammad Ghomi's user avatar
2 votes
0 answers
87 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 ...
Alexander Gelbukh's user avatar
4 votes
1 answer
339 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 ...
valle's user avatar
  • 864
2 votes
2 answers
365 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 ...
Ali Taghavi's user avatar
2 votes
1 answer
89 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 ...
Manfred Weis's user avatar
  • 12.6k
26 votes
3 answers
4k 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 $\...
Robin Houston's user avatar
7 votes
4 answers
690 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 ...
Taras Banakh's user avatar
  • 40.8k
10 votes
0 answers
432 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:=...
Taras Banakh's user avatar
  • 40.8k
5 votes
1 answer
2k 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 ...
WhatsUp's user avatar
  • 3,232
2 votes
1 answer
75 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 ...
user avatar
1 vote
1 answer
143 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)...
vkonton's user avatar
  • 175
5 votes
0 answers
272 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 ...
Caims's user avatar
  • 243
4 votes
0 answers
1k 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 ...
Joseph O'Rourke's user avatar
0 votes
1 answer
76 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 (...
user40780's user avatar
  • 867
7 votes
1 answer
352 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 ...
Dustin G. Mixon's user avatar
3 votes
0 answers
97 views

Optimally placing rectangles with obstacles

I am struggling with a fairly simple and natural geometric optimization problem, but I have not been able to find an obvious canonical method for solving it: I am given a collection of $m$ axis-...
Tom Solberg's user avatar
  • 3,929
3 votes
0 answers
62 views

Exact Value of a Constant Related to the Quickhull Algorithm

What is the exact value of the infinite sum $$ \sum_{n=1}^{\infty}n2^n\sin\left(\frac{\pi}{2^n}\right)\left(1-\cos\left(\frac{\pi}{2^n}\right)\right)$$ That constant is related to the Quickhull ...
Manfred Weis's user avatar
  • 12.6k

1
3 4
5
6 7
10