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
5
votes
2
answers
294
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 ...
- 7,194
3
votes
1
answer
212
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 ...
- 151k
13
votes
2
answers
664
views
Complexity of a weirdo two-dimensional sorting problem
Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
- 1,083
0
votes
1
answer
67
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,590
7
votes
5
answers
1k
views
How to compute the average distance till intersection within a triangle in $\mathbb{R}^2$?
You are given 3 points in $\mathbb{R}^2$; $A$, $B$, $C$ forming a triangle with area > 0. You pick an arbitrary point inside $ABC$ and an arbitrary direction. After some distance $d$, you will ...
CommunityBot
- 1
0
votes
1
answer
407
views
Parametrization of polygons and polyhedra [closed]
So, I've got a pretty interesting problem:
I was wondering how one would go about trying to generate every n-gon, or at least parametrize the space of a specific n-gon (say a hexagon) so it's easily ...
- 44.4k
7
votes
2
answers
527
views
Intersection of 2 visibility polygons
Let $P$ be a simple, closed and bounded polygon and $p_1,p_2 \in \mathrm{int}(P)$ be two points in its interior. Is it true that the intersection of the visibility polygons of $p_1$ and $p_2$ is ...
- 151k
2
votes
0
answers
97
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 ...
7
votes
2
answers
379
views
Number of edges in linklessly embeddable graphs
What is the maximum number of edges of an $n$-vertex linklessly embeddable graph?
A more general question is the following. What is the maximum number of edges of an $n$-vertex graph with Colin de ...
- 32.1k
4
votes
1
answer
354
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 ...
- 151k
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 4,713
2
votes
2
answers
399
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 ...
- 671
2
votes
1
answer
91
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 ...
CommunityBot
- 1
4
votes
2
answers
2k
views
Decomposing a polygon with holes
It is known that given a polygon $P$ with holes it is NP-hard to find a decomposition of $P$ into convex polygons, s.t. their number is minimized (even if Steiner points are allowed).
I am wondering ...
- 1,228
7
votes
4
answers
706
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 ...
- 41.9k
4
votes
1
answer
323
views
What properties does generalized Delaunay triangulation have?
Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...
- 4,713
10
votes
0
answers
441
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:=...
- 41.9k
5
votes
1
answer
237
views
Triangulation of the surface determined by sampling two of its cross-sections
I have a data set that essentially looks like the picture below, i.e., it's given by sets of points in $\mathbb{R}^3$ that sample the cross-sections of a certain surface that in principle I do not ...
- 151k
1
vote
1
answer
98
views
Inferring the properties of a visibility blocker tangential to a point-like light source
Imagine there's a point-like particle undergoing radioactive decay at some position $(0,0,0)$ in Euclidean $3$-space. We encapsulate this particle with a spherical detector for the decay products it ...
- 4,713
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 ...
- 20.8k
2
votes
1
answer
76
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 ...
- 151k
21
votes
8
answers
4k
views
Determine if circle is covered by some set of other circles
Suppose you have a set of circles $\mathcal{C} = \{ C_1, \ldots, C_n \}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius $r$...
- 151k
22
votes
2
answers
3k
views
Missing document request
I received a request for another long-lost document:
I am wondering if there is any way I
might obtain a copy of
The geometry of circles: Voronoi
diagrams, Moebius transformations,
...
- 151k
9
votes
1
answer
424
views
Hamiltonian circuit
Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior.
Let T be a triangulation of the whole disk with vertices on the labelled points such that T ...
CommunityBot
- 1
1
vote
1
answer
146
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)...
- 6,237
7
votes
2
answers
1k
views
The (Sigma) Algebra of Convex Sets
This is a question-by-proxy for a colleague from computer science. I'm sure many people here are already aware that convex decomposition forms an important sub-field of both computational geometry and ...
- 15.5k
4
votes
2
answers
3k
views
Computational geometry, tetrahedron signed volume
Short version: I'm trying to compute the orientation of a triangle on a plane, formed by the intersection of 3 edges, without explicitly computing the intersection points.
Long version: I need to ...
- 2,600
0
votes
2
answers
3k
views
Determine the boundary points of a set of points [closed]
I have a set of points $S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$. Then how to find the boundary points (which is a subset of $S$) of $S$?
There are methods like convex hull, concave hull and $\...
- 151k
-1
votes
2
answers
251
views
Incidences of quadratic forms and points [closed]
Is there anything that is known about what is the maximal number of incidences between quadratic forms and points? I looked at the internet and I haven't found anything that works for something that ...
- 151k
6
votes
2
answers
999
views
The straightest possible path embeddable in a path of polygons
I'm studying a problem involving the sets of discrete curves that can be embedded in a non-trivial polygon, from a source to a target point, as shown below.
Initially my interest was limited to the ...
- 4,713
3
votes
2
answers
1k
views
maximum number of shortest path among a set of n triangle obstacles
Assume that we have a two distinct points. The number of shortest path between these two points is one. When we add a triangle obstacle to the plane and this triangle intersects the line connecting ...
- 151k
4
votes
1
answer
3k
views
intersection of convex and non-convex polyhedra
I am trying to find the best appropriate way to intersect polyhedra which may be non-convex.
The number of vertices that build the polyhedron is hence always small (up to 20 or so).
The ...
- 151k
3
votes
2
answers
1k
views
Enclosing a set of ellipses within one ellipse
Is there an algorithm that takes in a set of ellipses and gives back an ellipse that encloses the original set of ellipses?
- 4,713
5
votes
0
answers
273
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 ...
- 151k
5
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 ...
- 151k
8
votes
1
answer
10k
views
Subtract Rectangle from Polygon
I'm looking for an algorithm that will subtract a rectangle from a simple, concave polygon and return a remainder of polygons. If the rectangle encloses the polygon, the remainder is null. In most ...
- 4,713
1
vote
1
answer
226
views
Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier
Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$.
Q1. What is the least time complexity
possible/known for recreating the
...
- 151k
4
votes
1
answer
300
views
Computable link invariants
I am interested in the following situation: given a braid $B$, it induces a link $L$ in a pretty straightforward way ("glue" the endpoints, like here). For a braid $B$, we know how to represent it in ...
- 28.2k
16
votes
2
answers
5k
views
Weighted area of a Voronoi cell
Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
8
votes
4
answers
1k
views
Shortest Path in Plane
I thought about the following problem:
Given a polygonal subdivision of the euclidian plane where each of the polygons has a speed associated with it, and given two points s,t, I'm interested in the ...
- 151k
0
votes
1
answer
79
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 (...
- 13.6k
7
votes
1
answer
362
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 ...
CommunityBot
- 1
2
votes
1
answer
823
views
Sequence of polygons containing the shortest path
Hello all,
I’m looking at the weighted region problem i.e. trying to find the shortest weighted path across a polygon subdivision, but at this point in my work, I only need to know the sequence of ...
CommunityBot
- 1
6
votes
2
answers
2k
views
Find minimum-area ellipse which encloses two ellipses
I need an efficient algorithm to find the ellipse with the smallest possible area which encloses two given ellipses. The given ellipses are constrained to have coincident centers at the origin but can ...
- 151k
3
votes
0
answers
100
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-...
- 4,049
3
votes
0
answers
63
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 ...
- 13.2k
2
votes
1
answer
280
views
Worst Case Region for a Convex Hull Heuristic
I am currently implementing a heuristic algorithm for planar convex hulls hand would like to know, for which kind of strictly convex region it exhibits worst performance.
I know that there are many ...
CommunityBot
- 1
2
votes
0
answers
49
views
Algorithm for Finding the Center of an Optimal Stereographic Projection
given a fnite set $\mathcal{P}$ of points on a $n$-sphere $\mathcal{S}$ and, define a function $f:(s,\mathcal{P})\mapsto\mathbb{R}_0^+$, that maps each point $s$ on $\mathcal{S}$ to the $n$-volume $...
- 13.2k
8
votes
1
answer
1k
views
How to generate Voronoi diagram with polygons of equal area?
I would like to generate some random set of points so that their Voronoi diagram consist of equal-area polygons. Is it possible to impose some constraints on the points in order to have the same areas ...
- 151k
5
votes
2
answers
755
views
Intersecting a convex polytope with the unit sphere
I have a list of $m$ affine inequalities in $n$ variables of the following form
$$a_1 x_1 + \cdots + a_n x_n \leq c_n$$
I would like to know whether there is any point on the unit sphere in $\...
