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.
0
votes
0answers
46 views
plotting parametrized algebraic curves near singularities
I have a parametrized algebraic curve:
x(t)=A(t)/D(t);
y(t)=B(t)/D(t);
with A(t) and B(t) being polynomials in t. The curve is solution of a linear system in two unknowns x and y with Cramer's ...
3
votes
0answers
124 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 ...
1
vote
0answers
88 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$ ...
3
votes
1answer
61 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?
5
votes
3answers
232 views
How hard is it to determine if a weighted graph can be isometrically embedded in R^3?
Consider a graph $G$ with nonnegative edge weights.
Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight?
...
5
votes
1answer
94 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 ...
5
votes
1answer
170 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 ...
1
vote
1answer
153 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 ...
1
vote
2answers
142 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 ...
3
votes
2answers
177 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$?
0
votes
0answers
67 views
minimizing the sum of euclidean norms with box constraints
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 ...
1
vote
0answers
41 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 ...
6
votes
0answers
61 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 ...
1
vote
1answer
54 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 ...
2
votes
2answers
131 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. ...
4
votes
1answer
117 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 ...
3
votes
1answer
126 views
Triangulations of a disk, flip distance and 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 ...
4
votes
0answers
154 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 ...
4
votes
2answers
174 views
point in polytope
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
3
votes
3answers
321 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 ...
1
vote
2answers
101 views
Incremental structure of a delaunay triangulation
This would probably be considered a reference request, as I would imagine it has been studied extensively in earlier work. Say I have a collection of distinct points $X = \{x_1,\dots,x_n\}$ in the ...
4
votes
1answer
223 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 ...
3
votes
2answers
300 views
Hyperrectangle partition of set of overlapping hyperrectangles
I have a set of $n$, $d$-dimensional hyperrectangles which may be overlapping in arbitrary ways. I would like to partition the area covered by this set into a set of non-overlapping hyperrectangles. ...
2
votes
1answer
156 views
Finding the vertices of a convex polyhedron from a set of planes
I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.
...
3
votes
0answers
62 views
Computing with Graphs in Surfaces
I asked this question yesterday on math.stackexchange, but the only response so far hasn't really addressed the question, so I thought I'd cross-post it.
I am currently working on a research project ...
17
votes
1answer
501 views
An NP-hard $n$ fold integral
We are given rational numbers $[c_1, c_2, \ldots, c_n]$ and $v$ from the interval $[0,1]$.
Consider the $n$-fold integral
$$
J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} ...
4
votes
0answers
143 views
Upper bounds on art gallery problems using independent witnesses
Given a polygon $P$, the art gallery problem looks to find a smallest set of points that sees all of $P$. One way of bounding the number of guards necessary (from below) is to find a largest set of ...
4
votes
1answer
370 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 ...
4
votes
1answer
261 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 ...
2
votes
1answer
58 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|c\in C$} for some $x\in R^d$ is called homothetic copy of $C$. The number
...
0
votes
0answers
36 views
Covering the annulus of symmetric convex body
Consider a symmetric convex body $A$ in $R^d$. Now, we draw another object, $A'$, concentric and translated with respect to A and having radius slightly greater than twice to the radius of $A$.
Now ...
3
votes
1answer
232 views
Algorithms for covering a rectilinear polygon using the same multiple rectangles
Sorry for the crossing-posting: original post is here
All angles of the polygon (representing a room) are right. It may be convex or concave. Use rectangles of the same size (representing a sensor ...
4
votes
1answer
277 views
Biggest ball included in an intersection of balls
I would like to prove that for any family of balls $\{B(c_i,r_i)\}_i \subset \mathbb{R}^d$ such that $\{c_1, \dots, c_n\} \subset \bigcap_i B(c_i,r_i) $ and $\forall i, r_i \geq 1$, there exists a ...
3
votes
1answer
103 views
Number of isomorphism classes of triangulations of a convex polygon
The number of triangulations of a convex $n$-gon is $C_{n-2}$ the $n-2$nd Catalan number. What I am wondering, is if there is a way to enumerate the isomorphism types of these as graphs? I am ...
2
votes
1answer
177 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 ...
35
votes
0answers
505 views
Reasons to prefer one large prime over another to approximate characteristic zero
Background:
In running algebraic geometry computations using software such as Macaulay2, it is often easier and faster to work over $\mathbb F_p = \mathbb Z / p\mathbb Z$ for a large prime $p$, rather ...
0
votes
2answers
225 views
Higher dimensional convex hull
Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as ...
1
vote
1answer
77 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 ...
1
vote
0answers
88 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 ...
6
votes
2answers
292 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 ...
3
votes
1answer
106 views
The discrete theory of compressible fluids dynamics
I am working on the discrete theory of compressible fluids dynamics, i.e., numerically solving and simulating the compressible fluids , we are interested in the way using discrete exterior calculus, ...
0
votes
2answers
167 views
Incidences of quadratic forms and points
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 ...
1
vote
0answers
88 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 ...
3
votes
2answers
230 views
Questions on Discrete Exterior Calculus in numerial computing
I have several questions about the Discrete Exterior Calculus (DEC) in the numerical method for solving partial differential equation in physics:
(Discrete Exterious Calculus is the newly developed ...
1
vote
1answer
43 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 ...
3
votes
1answer
141 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 ...
7
votes
0answers
139 views
Fractional Helly for more than one piercing
Fractional Helly Theorem says the following:
For every $0<\alpha\leq 1$ there exists $\beta = \beta(d, \alpha)$ with the following property. Let $C_1 , C_2 , ..., C_n$ be convex sets in $R^d$, $n ...
3
votes
1answer
177 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 ...
2
votes
3answers
1k 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
vote
2answers
383 views
Projection of a point to a convex hull in d dimensions
Hi,
I've got n points in d dimensions (typically n is around 30k-60k and d is 5 or 6). I'm using qhull to calculate the Delaunay triangulation and the convex hull of the set of points.
You can ...
