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

4
votes
2answers
54 views

Expressing a convex Polytope as a sublevel set of a function

Given an n-dimensional polytope $P$ in $\mathbb R^n$, Given as a convex hull of a finite set of points, $S$ I would like to construct an expliict formula for a function $f\colon \mathbb R^n \to ...
5
votes
0answers
66 views

Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell

Given an $n \times n$ grid with unit grid cells, and one point from the interior of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...
5
votes
2answers
494 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 ...
2
votes
0answers
196 views

Find minimum-area ellipse enclosing a set of ellipses, all centered at the origin

Given a set of N > 2 (two-dimensional and coplanar) ellipses, all centered at the origin, how do I find the ellipse with the minimum area which encloses all of them? Background: Thanks to Will Jagy ...
4
votes
2answers
206 views

Breaking a rectangle into smaller rectangles with small diagonals

Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...
4
votes
2answers
236 views

What are the applications of Voronoi diagrams in pure mathematics? [closed]

Voronoi diagrams have interesting mathematical properties and applications in algorithms and modeling. But what are its applications in pure mathematics? For example, what theorems can be proved using ...
7
votes
1answer
174 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 ...
4
votes
2answers
71 views

Construct polygon/polyhedron containing all points not externally visible w.r.t given polygon/polyhedron?

Is there an algorithm to construct a polyhedron containing all points in space for which there exists no ray to infinite not intersecting a given polyhedron? In 2D, we could consider polygons. For ...
4
votes
1answer
239 views

Finding the “top” or “bottom” vertex of a simplex

A vertex $v$ of a simplex in $\mathbb{R}^n$ is a "top" vertex if there exists a point $p \neq v$ in the simplex with $v \ge p$ (i.e. $v_1 \ge p_1$, ... , $v_n \ge p_n$). Similarly, $v$ is a "bottom" ...
5
votes
3answers
2k views

Minimum distance between two arbitrary circles in space?

What is the minimum distance between two arbitrary circles in space? I am working out the problem with Maxima, but I am surprised by how complicated this rapidly turns out to unfold for such a ...
5
votes
1answer
95 views

Algorithm that generates minimum n-simplex that cover n-cube?

Given an $n$-cube with unit volume, is there any algorithm that generates a minimum volume $n$-simplex that covers the $n$-cube?
3
votes
1answer
87 views

Computionally efficient vertex enumeration for (convex) polytopes

Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...
2
votes
2answers
1k views

Trilateration problem

When trying to develop an algorithm for a program, I got with the following problem: Determine the approximate location of $O$, if you can take finite samples $P_n$ from known locations and always ...
1
vote
1answer
167 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 ...
9
votes
3answers
677 views

Is every graph an edge-crossing graph?

Consider a circular drawing of a simple (in particular, loopless) graph $G$ in which edges are drawn as straight lines inside the circle. The crossing graph for such a drawing is the simple graph ...
10
votes
0answers
130 views

Dividing a convex region to minimize average distances

Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...
2
votes
0answers
78 views

The intersection of two $l_1$ balls

Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ with respect to the $l_1$ norm that have different radii and different centers. Is there an upper bound for the number of vertices that $B_1\cap ...
6
votes
1answer
128 views

Angle subtended by the shortest segment that bisects the area of a convex polygon

Let $C$ be a convex polygon in the plane and let $s$ be the shortest line segment (I believe this is called a "chord") that divides the area of $C$ in half. What is the smallest angle that $s$ could ...
2
votes
0answers
109 views

Intersecting balls with convex regions and a bisector thereof

This question is related to my previous posting Angle subtended by the shortest segment that bisects the area of a convex polygon Let $C$ be a convex region in the plane and let $s$ be the shortest ...
1
vote
0answers
39 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 ...
2
votes
0answers
82 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 ...
2
votes
3answers
815 views

Is there a simple criterion to determine if two parallelograms intersect?

Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty? Note that I do not need to actually find the intersection.
0
votes
1answer
85 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 ...
23
votes
4answers
3k views

Computational software in Algebraic Topology?

I was wondering if there is any good software out there that allows you to do specific computations in algebraic topology. For example: Create a simplicial complex/set and ask questions about its ...
0
votes
2answers
290 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 ...
3
votes
2answers
94 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
vote
0answers
25 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 ...
2
votes
1answer
90 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 ...
2
votes
1answer
58 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. ...
2
votes
1answer
351 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 ...
13
votes
1answer
326 views

Are all well behaved “mean” functions on $\mathbb{R}^+$ equivalent?

Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties: $M(a,a)=a\qquad$ (identity) $M(a,b)=M(b,a)\qquad$ (commutativity). and possibly ...
1
vote
2answers
222 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 ...
4
votes
1answer
217 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 ...
0
votes
0answers
53 views

Any software that can symmetrize input sets?

Is there any software that contains symmetrization techniques ex. polarization, Steiner Symmetrization etc. I suppose not. Which software would you suggest for rigid transformations? Thank you
7
votes
2answers
5k views

Partitioning a polygon into convex parts

I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible. I know almost nothing about this subject, so I've been searching on Google ...
7
votes
0answers
128 views

Nearest Point to a real algebraic set

Suppose I have a compact bounded real algebraic (eventually: or analytic or semialgebraic or semianalytic set) $V$ in $\mathbb R^3$ and a point $x\in\mathbb R^3$ not in $V$. How much do we know about ...
2
votes
3answers
1k views

Formulas for equidistant curves

Hello, 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 ...
2
votes
1answer
86 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 ...
2
votes
1answer
70 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 ...
1
vote
1answer
142 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. ...
1
vote
3answers
5k views

Get a point inside a polygon

I have a 2D polygon of arbitrary geometry. I need to find any point that is inside of that polygon. Taking the center won't work, because the polygon might not be convex. Is there a way to quickly ...
8
votes
1answer
246 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 ...
5
votes
1answer
720 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 ...
0
votes
1answer
127 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) ...
0
votes
2answers
331 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 ...
2
votes
1answer
145 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$) ...
1
vote
0answers
49 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 ...
0
votes
0answers
137 views

Trilateration issues, when circles don't intersect

I'm working on Indoor localization where I've deployed multiple iBeacons in my environment. I'm taking distances from all the beacons through their RSSI values. They are not 100% accurate though. Now ...
2
votes
3answers
408 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 ...
6
votes
4answers
825 views

How to compute the average distance till intersection within a triangle in R^2?

Lots of simple questions because I am a noob. You are given 3 points in R^2; A, B, C forming a triangle with area > 0. You pick an arbitrary point inside ABC and an arbitrary direction. After some ...