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.

learn more… | top users | synonyms

1
vote
1answer
67 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
199 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
128 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
169 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 ...
3
votes
0answers
276 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
220 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 ...
4
votes
3answers
570 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
106 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
241 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
479 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
403 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
76 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
545 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
176 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 ...
5
votes
1answer
654 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
336 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
85 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 ...
0
votes
0answers
37 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 ...
4
votes
1answer
362 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
213 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 ...
4
votes
1answer
312 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
134 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
297 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 ...
46
votes
2answers
1k 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
247 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
80 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
96 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
341 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
129 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
175 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
97 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
302 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
53 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
148 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
141 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
204 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
2k 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
804 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 ...
3
votes
2answers
518 views

Find longest segment through centroid of 2D convex polygon?

Given a 2D convex polygon P and its centroid C, how do I find the longest line segment passing through C, where the endpoints of the segment lie on the boundary of P? Intuitively I imagine there ...
3
votes
1answer
1k 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 ...
0
votes
0answers
212 views

Determining the simplices in freudenthal triangulation

HI, I have a doubt on Freudenthal Triangulation. I want to partition a simplex into finer simplices. The FT gives me the vertices of the simplices which partition my original simplex into ...
1
vote
0answers
346 views

Solving 3D equation system (inverse-projecting a triangle)

Please, how is the equation system below named exactly (to search further literature)? Does it have an analytical solution? If it doesn't, then what could be the fastest numerical method for it ...
1
vote
0answers
154 views

Compute generalized pentagram map

Hi, (This is my first question on MathOverflow! :-) Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", ...
10
votes
3answers
485 views

Algorithms in Invariant Theory

Let $V$ be a polynomial representation of the general linear group $\Gamma:=\DeclareMathOperator{\Gl}{Gl}\Gl_n(\newcommand{\C}{\mathbb C}\C)$. In chapter 4.6 of his book "Algorithms in Invariant ...
5
votes
5answers
579 views

Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

A friend asked me to post the following question. He's not an MO user and felt it would be better received if asked by someone who was already known to the community. This is not my area, but I'll do ...
7
votes
1answer
2k 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 ...
8
votes
2answers
2k views

Covering a Polygon with Rectangles

I am tyring to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle. I thought about ...
3
votes
2answers
424 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 ...
2
votes
2answers
579 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
vote
0answers
150 views

Techniques for refining or constraining a Voronoi diagram?

I have a dataset coming from weather stations where each vertex used to generate the Voronoi diagram is the lat/long of the station. As such, each cell represents the area whose weather is being ...