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
1
vote
0
answers
73
views
Concise disambiguation of Voronoi boundaries
Say that $x_1,\dots,x_n$ are points in the plane, with a Voronoi diagram $V_1,\dots,V_n$. The Voronoi diagram is typically defined by $$V_i = \{x:\|x-x_i\|\leq \|x-x_j\|~\forall j\}~.$$ Is there any ...
- 113
3
votes
0
answers
169
views
Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)
Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of $...
- 6,210
0
votes
1
answer
123
views
Practical Algorithm for Comparing the Discrepancy of Point Sets (on Unit Hyper Spheres)
I have devised a simple geometric algorithm for generating a sequence of points on unit hyper spheres; that algorithm depends on a single real parameter, which I would like to optimize in order to get ...
CommunityBot
- 1
1
vote
2
answers
667
views
algebraic topology and 3d/4d printing [closed]
I googled for papers on applying algebraic topology to 3d/4d printing. It just seems to me that there has to be a connection. Any help, kind audience?
edit: 4d printing means 1-parameter families of ...
- 26.3k
5
votes
2
answers
630
views
Average vertex degree in finite Delaunay triangulations in high dimensions
In $\mathbb{R}^2$ it's known that with a "random" point configuration, the average degree of a vertex in its Delaunay triangulation is 6.
Does anyone know of a similar result in higher dimension? I ...
- 1,502
1
vote
0
answers
43
views
Determining feasibility of specific intersection structures between closed paths in the plane
I have two arrays, each containing a different ordering of the same set of integers. Each integer is a label for a point in which two closed paths intersect in the plane. The two arrays are ...
- 11
2
votes
1
answer
115
views
mean length of the non-crossing graphs on n points
My original question is rather vague so I'll start with a precise example and then indicate possible generalisations.
Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...
CommunityBot
- 1
2
votes
1
answer
107
views
What is Known about Preprocessing for Stabbing Queries?
In a concrete setting, I have the following problem:
given a fixed set of simple objects (e.g. disks or, convex polygons with few vertices), I need to quickly report the objects that are hit (i.e. ...
- 151k
6
votes
1
answer
2k
views
Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?
Not sure whether this question belongs here or math.stackexchange.
You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
- 6,210
1
vote
2
answers
681
views
Regular paths along surface of sphere
I'm trying to create a program where a small ball is supposed to move along the surface of a sphere, which is given by its radius $r$ and the center $c$.
The movement should be repetitive, so that ...
CommunityBot
- 1
4
votes
1
answer
367
views
convex polyhedron in the unit cube
Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where $\...
- 6,210
2
votes
1
answer
115
views
Covering the annulus of d-cube
Given a convex body $C\subset R^d$ and a positive real $\lambda$, any set of the form $\lambda C + x = \{ \lambda c+x \mid c\in C \}$, for some $x\in R^d$, is called a homothetic copy of $C$. The ...
- 6,210
2
votes
1
answer
173
views
Calculating the "Belvedere Hull" of a Simple Planar Polygon
As an informal motivation the problem, imagine a tower with polygonal footprint, that is located in a beautiful landscape, the "Belvedere Hull" is then related to the directions, in which one would ...
- 151k
2
votes
1
answer
320
views
NP hard problems on UD graphs
I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard.
http://ac.els-cdn....
- 940
8
votes
1
answer
1k
views
Dubins car shortest paths: Decidable?
A Dubins car follows a
Dubins path
in $\mathbb{R}^2$, with constant wheel speed and
limited turning radius.
It is known that the shortest Dubins path in the absence
of obstacles follows circular
arcs ...
- 151k
0
votes
1
answer
245
views
Exploiting the Linearity of the Pullback [closed]
Edit: This question has been significantly revised.
Some recent developments in computational geometry (for example see http://geometry.stanford.edu//papers/fmfrmbs-obsbg-12/fmfrmbs-obsbg-12.pdf) ...
- 34.7k
2
votes
1
answer
586
views
Inverse Problem for Pullback
Let $M$ and $N$ be smooth manifolds and $T: M \to N$ be a smooth map. Let $ \mathcal{F}(M,\mathbb{R})$ (resp.$ \mathcal{F}(N,\mathbb{R})$) denote the space of smooth functions from $M$ (resp. $N$) ...
- 8,597
1
vote
0
answers
91
views
Representing a Pullback as an Infinite Matrix
Let $M$ and $N$ be manifolds and let $T: M \to N$ be a bijective map. Let $ \mathcal{F}(M,\mathbb{R})$ (resp.$ \mathcal{F}(N,\mathbb{R})$) be the space of all functions from $M$ (resp. $N$) to $\...
- 61
2
votes
3
answers
490
views
find the collision of a particle with a swept triangle.
Given there is triangle: V in 3D space that transforms over time t -> t1 to V1, and a static point P is somewhere in 3d space, how can I determine if P ever collides with V, and if so at what value of ...
- 151k
1
vote
1
answer
558
views
Is there a Gröbner basis analogue that exists for vector spaces?
Suppose I have a coordinate system $t_1,\ldots t_N$ with a lexicographical ordering. Let LT denote choosing the lowest term of a polynomial with respect to this ordering. e.g. LT$(t_1 + t_2)=t_2$.
...
- 131
1
vote
0
answers
66
views
Non-Convex Polygons with "Antipodal Visibility"
by "antipodal visibility" of planar, simple polygons I mean the following property:
if two points $p$ and $q$ on the polygon's boundary divide the polygon's boundary into two polylines of equal length,...
- 13.2k
3
votes
0
answers
391
views
Dissection of a polygon into convex polygons
Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...
- 935
12
votes
1
answer
2k
views
Ways to show a system of polynomial equations has no solution
I came across the following system of polynomial equations on $X_1,\dots,X_{m-2}$:
$$
\begin{cases}
2X_{2s}+\sum\limits_{t=1}^{2s-1}(-1)^tX_tX_{2s-t}=0,\quad s=1,\dots,\frac{m}{2}-1,\\
X_sX_{m-s}+(-1)^...
- 767
0
votes
1
answer
116
views
Paper on unit disk graphs
I was wondering if anybody knows of a 'link' to the paper by Marathe 1995 et al on analysis of the greedy algorithm for finding a Max independent set in Unit Disk Graphs?
- 188k
2
votes
2
answers
144
views
Complexity of Untwisting Polygons
What is the complexity of the following task:
given a sequence $p_1, ..., p_n, p_1$ that defines a closed polyline in the euclidean plane,
what is the complexity of finding a reordering of the points, ...
- 13.2k
5
votes
2
answers
372
views
Random Vornoi Diagrams (particular measures)
This is my second question about Random Voronoi diagrams, in my first question was given some excellent advice but i was not clear in explaining what i was looking for.
I'm interested to know ...
CommunityBot
- 1
10
votes
2
answers
1k
views
Random Voronoi Diagrams
I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm ...
- 151k
2
votes
1
answer
387
views
Hilbert function of points in $\mathrm{P}^2$
Let $\Gamma$ be a collection of $d$ points in $\mathrm{P}^2$, and $I$ the graded ideal of $\Gamma$.If
$$
\mathrm{gin_{rlex}}(I)=(x_1^k,x_1^{k-1}x_2^{\lambda_{k-1}},...,x_1x_2^{\lambda_1},x_2^{\...
- 4,484
3
votes
1
answer
429
views
Finding a minimum covering of a polygon with interesting shapes
After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of ...
- 151k
3
votes
0
answers
58
views
Find shift direction for min overlap area of 2 polygons
I have 2 arbitrary polygons (concave or convex) with certain overlap.
Now there is some relative shift between these 2 polygons (vector s with a constant length).
I want to find the direction of s ...
- 31
3
votes
2
answers
333
views
Combinatorial design for minimization problem over binary strings
Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
- 19k
3
votes
0
answers
149
views
Dead Flies Problem [duplicate]
If a set of points in the plane contains one point in each convex region of
area 1, then can it have finite density?
what is the density of the points? In my understanding, it means the average ...
CommunityBot
- 1
3
votes
1
answer
141
views
Number of lattice polytopes contained in a given lattice polytope?
Given a (convex) lattice polytope, suppose we want to list or count all (convex) lattice polytopes (of the same dimension) contained in it. Are there efficient ways to do this?
- 151k
6
votes
1
answer
301
views
Software computation with arithmetic schemes
For rings such as $\mathbb{Z}[x,y]$ is there software to compute any of:
1.) The integral closure of $\mathbb{Z}[x,y]/(f)$. de Jong has a very general algorithm that works in this context (http://...
- 121
5
votes
1
answer
251
views
Simultaneous geometric separator
A geometric separator is a line that separates a given set of shapes to two subsets of approximately the same size (up to a constant), while intersecting only a small number of shapes. When a ...
- 3,549
2
votes
2
answers
2k
views
Anuloid (Torus) x line intersection
Hi,
I need calculate ray (line) intersection with torus for my ray-tracing program (I know, its to graphics, but i need math behind it).
I can solve equation of order x^4, but thats too way slow (...
CommunityBot
- 1
5
votes
1
answer
369
views
Given a polygon with holes, find a maximum distance pair in two subsets
I am curious about the following problem:
Given a polygon with holes and two convex subsets, $S$ and $T$, find points $s \in S, t \in T$ such that the shortest path between the two points has maximal ...
- 151k
3
votes
1
answer
1k
views
Explicit computation of the action of a Dehn twist on the fundamental group of a surface
Let $S$ be a compact orientable surface of genus $g$. Now let $p\in S$ and $\gamma$ a closed simple curve on $S$ disjoint from $p$. It is not very difficult to compute the action of a Dehn twist along ...
- 28.2k
2
votes
2
answers
333
views
A Claim on Typical Voronoi Cells
I am trying to prove the following claim (may be it has been proven).
Claim: Consider a set of points $\phi=\{x_1,x_2,...,x_i,...\}$ generated by a homogeneous PPP with rate $\lambda$ in the 2-D plane ...
CommunityBot
- 1
4
votes
3
answers
3k
views
Intersection of Polyhedra
I'm writing a collision detection algorithm, and so far I've been using Joseph O'Rourke's book "Computational Geometry in C" as reference. It outlines an algorithm to determine whether a point is ...
3
votes
2
answers
1k
views
Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances
Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances.
The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?
- 7,276
1
vote
0
answers
526
views
minimizing the sum of euclidean norms
minimizing the sum of euclidean norms with box constraints
I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...
- 13
1
vote
0
answers
58
views
Covering a set of points by bounded geometric object/objects
1) Let $S$ be a set of $n$ points in $R^d$. Now, given a bounded geometric object $G$, the problem is to check whether $S$ can be contained in $G$.
2) Also, in general setting, the problem is to ...
- 285
6
votes
0
answers
114
views
Constructing a polyhedron of maximal possible volume from given bounds on areas of its faces
Consider $n$ variables $a_1,...,a_n$ ranging over $\mathbb{R}^+$. Suppose we are given $n$ pairs of positive rational numbers $(p_1,q_1),...,(p_n,q_n)$ where each pair imposes bounds on the ...
- 161
1
vote
1
answer
85
views
Smoothly deforming a set of three-dimensional points
I want to deform a 3D mesh according to 3 or more control points, meaning that the transformation is constituted by pre-images $c_i$ and images $c_i'$ of these control points. Each point of the mesh ...
- 151k
4
votes
2
answers
580
views
Largest inscribed rectangle inside a convex polygon
It has been proved by Radziszewski in this paper
K. Radziszewski. Sur une probleme extremal relatif aux gures inscrites et circonscrites aux gures convexes. Ann. Univ. Mariae Curie-Sklodowska, Sect. ...
- 675
5
votes
1
answer
176
views
Maximal geometric mean of distances between points on an interval
Suppose I had T points in the interval $[0,1]$. Call them $e_1, \dots, e_T$.
Question 1:
What is a good nontrivial bound on the geometric mean of $$\{|e_i - e_j| : 1 \leq i < j \leq T \}, $$ as a ...
- 6,210
5
votes
0
answers
783
views
Intuition behind minimizing the Dirichlet energy of a mapping
What does minimizing the Dirichlet energy of a mapping $\Phi$ achieve intuitively?
Roughly it is the integral (or sum, if discrete) of $|\nabla \Phi(\;)|^2 dV$, with $V$ the volume.
So is it, in some ...
- 151k
3
votes
1
answer
1k
views
Regularity of Delaunay triangulation of a hypercube
First using a three dimensional unit cube as an example for the term "regularity", we can have two possible triangulations:
(A)
(B)
We say the lower triangulation is more "regular" than upper ...
- 1,502
4
votes
1
answer
821
views
Checking if a binary vector lies in the affine span of given binary vectors
Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in ...
CommunityBot
- 1