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.
503 questions
7
votes
1
answer
3k
views
Any reference to an algorithm for finding the largest empty circle on a sphere (with great-circle distance)?
Given a set $S$ of 2D points in the plane, there are known algorithms for finding the largest empty circle ($LEC$) of the set of points.
The $LEC$ problem is stated in this way: find a $LEC$ whose ...
- 151k
1
vote
1
answer
95
views
Uniformly sampling the solution space for points where the free termini of two rays, anchored at 3-space points, can intersect
I have two rays, one of length $L_1$ and one of length $L_2$. I anchor these rays, each at one end, on the 3-space points $p_1$ and $p_2$. Assuming that the Euclidean distance between $p_1$ and $p_2$...
- 4,713
6
votes
4
answers
752
views
Algorithm for k-medians in a convex polygon
Are there any known approximation algorithms or exact solution schemes for the k-medians problem in a convex polygon? That is, placing a collection of points $p_1,\dots,p_k \subset \mathbb{R}^2$ in a ...
- 4,713
1
vote
0
answers
179
views
Boundary surfaces in a 3d Voronoi tessellation with obstacles
Let $x_1,\dots,x_n$ be a set of points in $\mathbb{R}^3$ and let $\mathcal{O}_1 ,\dots, \mathcal{O}_m$ denote a set of polyhedral obstacles. What is the name for the surfaces that describe the ...
- 4,713
2
votes
1
answer
110
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 |...
- 6,337
5
votes
0
answers
350
views
Are nearby points in an algebraic curve necessarily connected?
I would like a result of the following form:
For every algebraic curve $C$ in $\mathbb{R}\mathbf{P}^{n-1}$, there exists an
explicit and easy-to-compute $\epsilon=\epsilon(C)>0$ such that ...
- 7,633
0
votes
0
answers
89
views
Why there isn't lexicographically smallest solution to a bounded linear program?
I am learning computational geometry when I run into this confusion. "A bounded 2D linear program may not have a lexicographically smallest solution", as the book says. I wonder why? I think we can ...
- 1
4
votes
2
answers
145
views
Complexity of Determining the Edges of Planar Convex Hulls
Question:
can the set of edges that resemble the convex hull ($CH$ for short) of $n$ points in the euclidean plane be determined in $O(n)$ time?
I know that the time complexity of determining the $CH$...
CommunityBot
- 1
3
votes
0
answers
61
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 ...
- 351
4
votes
2
answers
481
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 ...
- 18.6k
5
votes
1
answer
234
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 ...
CommunityBot
- 1
6
votes
5
answers
4k
views
Formulas for equidistant curves
I'm trying to draw on the computer a curve that keeps always the same distance(given as parameter) from a given curve. I know the formula for the given curve. I tried moving perpendicular to the first ...
- 101
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 ...
- 297
1
vote
1
answer
520
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 $\...
- 151k
7
votes
0
answers
122
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 ...
- 4,535
2
votes
1
answer
349
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$....
CommunityBot
- 1
4
votes
2
answers
440
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,001
3
votes
1
answer
516
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 ...
- 151k
2
votes
1
answer
69
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,...
- 151k
4
votes
2
answers
734
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{...
- 12.7k
5
votes
2
answers
435
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 ...
- 479
4
votes
2
answers
425
views
Algorithm for Reconstructing Point Sites from a Voronoi Diagram
how can one construct a finite set of points in the euclidean plane from its Voronoi Diagram and, what is the complexity of the problem?
- 151k
2
votes
2
answers
124
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 ...
- 23.7k
3
votes
2
answers
381
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 ...
- 6,891
4
votes
2
answers
805
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 ...
- 4,713
3
votes
1
answer
99
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 ...
- 128k
2
votes
2
answers
171
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 ...
- 1,462
5
votes
2
answers
440
views
Ascertain properties of a new kind of rectilinear-convex set
PREABMLE TO MY QUESTION
I am reading about convex sets and hulls in orthogonal/rectilinear spaces. As can be seen in this publication, for a given set of points in $\mathbb{R}^{2}$, there are many ...
CommunityBot
- 1
27
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 $\...
- 101
3
votes
1
answer
119
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 ...
- 151k
4
votes
3
answers
957
views
Questions on Discrete Exterior Calculus in numerical computing
I have several questions about Discrete Exterior Calculus (DEC) in numerical methods for solving partial differential equations in physics:
(Discrete Exterious Calculus is a newly developed subject ...
- 201
4
votes
2
answers
349
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 ...
- 151k
5
votes
1
answer
445
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'...
- 151k
2
votes
0
answers
111
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 ...
- 374
2
votes
2
answers
687
views
Where to submit a new convex hull algorithm?
Recently, I devised a new convex hull algorithm. Is there any forum where I can submit my work?
- 4,713
15
votes
2
answers
3k
views
Given the vertices of a convex polytope, how can we construct its half-space representation?
Let us say I have the vertices of a polytope $V = \{v_1,\dots,v_k\} \subset \mathbb R^n$. Is it possible to write $V$ as intersection of half-spaces using the information from the vertices, i.e., can ...
6
votes
1
answer
2k
views
Approximation of convex hull in high dimension
What are efficient methods (polytime) to compute an approximation of the convex hull in high dimension (say, $30000$) for a given set of points?
Edit:
I am looking for an algorithm for getting the ...
4
votes
0
answers
123
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
117
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, ...
- 601
1
vote
2
answers
269
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 ...
CommunityBot
- 1
1
vote
1
answer
130
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}...
- 13.2k
10
votes
1
answer
9k
views
Get Largest Inscribed Rectangle of a Concave Polygon
I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon.
In other words, I want to ...
- 4,713
6
votes
1
answer
508
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?
- 156k
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 ...
- 2,558
11
votes
5
answers
1k
views
Segments of Voronoi Diagrams on smooth manifolds. Are they geodesics?
Let $S$ be a patch of a smooth 2-manifold in $\mathbb{R}^3$, and pick two distinct points $a,\ b \in S$. Let $c$ be the set of points on $S$ equidistant to $a$ and $b$, where distance is defined by ...
- 1,228
1
vote
0
answers
99
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 ...
- 23.2k
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 ...
- 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 ...
- 1,171
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 ...
- 151k
2
votes
3
answers
6k
views
Intersection of Cones in Three Space
In several branches of applied mathematics the problem arises to describe the intersection of two cones in three space.
I have searched and found a few references that discuss the problem for cones ...
- 1,228