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

43
votes
2answers
944 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 ...
19
votes
4answers
2k 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 ...
17
votes
1answer
519 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} ...
16
votes
9answers
2k 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 ...
16
votes
2answers
2k 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, ...
16
votes
1answer
1k views

What can be said about the Shadow hull and the Sight hull?

This is a question implicitly raised by Is the sphere the only surface all of whose projections are circles? Or: Can we deduce a spherical Earth by observing that its shadows on the Moon are always ...
13
votes
1answer
2k views

How to efficiently vacuum the house

Let $P$ be a polygon (perhaps with no acute angles inside) and let $L$ be a line segment. The segment may move through the area inside $P$ in straight lines, orthogonal to $L$, or it may pivot on any ...
13
votes
2answers
894 views

Subfields of a function field

Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...
11
votes
3answers
472 views

finding the most-isolated point in a high-dimensional cube

I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find $\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} ...
11
votes
2answers
2k 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$. ...
10
votes
1answer
518 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 ...
10
votes
3answers
449 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 ...
9
votes
3answers
394 views

Degree of generators of irreducible components

Let $V$ be a Zariski-closed subset of $\mathbb{A}^n_k$, where $k$ is an algebraically closed field. Assume that $V$ may be defined by polynomials of degree at most $d$ (or to put it otherwise $V$ is ...
8
votes
3answers
762 views

Complexity of matching red and blue points in the plane.

I'm just asking because I'm curious. I was seeking references on the following problem, that a friend exposed to me last holidays : Problem Given $n$ red points and $n$ blue points in the plane in ...
8
votes
3answers
2k views

n-dimensional voronoi diagram

Hi, I need to compute the voronoi diagram of a set of points in $R^n$. I'm quite unschooled on the topic, could someone point me to the right references so that I can a) understand the theory behind ...
8
votes
2answers
257 views

Computational methods for dealing with geometrically complicated solid boundaries in fluid-air interface problems

Hello, I am a PhD student who does not have extensive computational experience seeking advice from those experienced with computational modelling as to which method would be most appropriate for ...
8
votes
1answer
538 views

Can taking the projective closure of an affine variety increase the degrees of its ideal generators?

Say we have some equations $f_1(x)=0, \ldots f_k(x)=0$ defining a variety $X$ in ${\mathbb C}^n$ (not necessarily a minimal number of generators, and not necessarily of minimal degree), and suppose we ...
8
votes
1answer
213 views

inferring the slope of a digitized line

Given real numbers $a$ and $b$, and an integer $n \geq 2$, let $f(n,a,b)$ be the minimum of $(nint(ja+b)-nint(ia+b)+1)/(j-i)$ (for $1 \leq i < j \leq n$) minus the maximum of ...
7
votes
2answers
757 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 ...
7
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 ...
7
votes
0answers
140 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 ...
6
votes
4answers
680 views

Shortest Path in Plane

Hi 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 ...
6
votes
3answers
248 views

Minimum separating subdivision in Plane

Hi I was thinking about the following problem: Given a planar Graph embedded in the plane and a set of points $P$ contained in the faces (no face contains more than one point) I want to determine ...
6
votes
4answers
646 views

Algorithm for k-medians in a convex polygon

Are there any known approximation algorithms or exact solution schemes for the k-medians problem in a convex polygon? That is, placing a collection of points $p_1,\dots,p_k \subset \mathbb{R}^2$ in a ...
6
votes
2answers
321 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 ...
6
votes
2answers
787 views

Conic hulls and cones

Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next ...
6
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 ...
6
votes
0answers
73 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 ...
5
votes
5answers
510 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 ...
5
votes
3answers
260 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
3answers
1k views

Random Sampling a linearly constrained region in n-dimensions…

Hi, So here is my problem: Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$ $x_n \le c_n$ and $\sum_{n=1}^N x_n = 1$ find an ...
5
votes
1answer
383 views

Intersections of irreducible components

Let $V$ be an algebraic variety (not irreducible) over $\mathbb{C}$, defined by an ideal $I = \{f_1,f_2,\dots, f_n\}$. $V$ is not necessarily pure dimensional. Suppose $V = R_1\cup R_2\cup\dots\cup ...
5
votes
2answers
979 views

Light rays bouncing around inside a sphere in d-dimensions

Suppose $S=\mathbb{S}^d$ is a unit sphere in $(d-1)$ dimensional space, with $d=3$ of special interest. The surface of $S$ is a perfect (internal) mirror. You stand at point $x$ (not the sphere center ...
5
votes
3answers
283 views

What is the most general class of metric spaces for which the closest pair of points in a finite subset can be found in time O(n^(1+eps))?

What is the most general class of metric spaces for which the closest pair of points in any finite subset can be found in time O(n^(1+eps))? I have studied how to do this in O(n log(n)) in the plane, ...
5
votes
1answer
579 views

Algorithm for embedding a graph with metric constraints

Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide if there is an ...
5
votes
1answer
117 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
175 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 ...
5
votes
1answer
591 views

Minimizing variance of distances between points when mean distance is fixed

In Rd, I have n > d+1 points. The mean distance between pairs of points is 1. How can I minimize the variance of the distances (equivalently, the mean squared distance)? I'm mainly interested in d ...
4
votes
5answers
614 views

Segments of Voronoi Diagrams on smooth manifolds. Are they geodesics?

Let $S$ be a patch of a smooth 2-manifold in $\mathbb{R}^3$, and pick two distinct points $a,\ b \in S$. Let $c$ be the set of points on $S$ equidistant to $a$ and $b$, where distance is defined by ...
4
votes
1answer
3k 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 ...
4
votes
3answers
672 views

Area-preserving map between rectangles and fat polygons

Are there any well-known continuous area-preserving maps between fat convex polygons and fat rectangles? Specifically, given a fat convex polygon $C$, is there a natural way to choose a fat rectangle ...
4
votes
2answers
197 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
1answer
209 views

Checking if one polytope is contained in another

Hi, 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
votes
2answers
457 views

Area ratio of a minimum bounding rectangle of a convex polygon

Take a convex polygon $P$ in the plane, and find its minimum area bounding rectangle, $R$. I'm interested in the ratio of the area of $R$ to the area of $P$. The ratio has a minimum of $1$ for ...
4
votes
1answer
205 views

“Average” Voronoi diagrams without probability?

A plane Poisson process with uniform intensity scatters "sites" about the plane. If I'm not mistaken, in a sense the "average" Voronoi diagram of that set of sites is a honeycomb. I know it's been ...
4
votes
1answer
253 views

Are point sets of the same order type connected by continuous (order type)-preserving motion?

Given two general position point sets in $\mathbb{R}^2$ of the same size and order type, is it possible to continuously move the points of one set until they coincide with those of the other set in ...
4
votes
1answer
1k views

intersection of convex and non-convex polyhedra

Hi everyone, 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). ...
4
votes
1answer
123 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 ...
4
votes
1answer
290 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 ...
4
votes
1answer
463 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 ...