# Tagged Questions

**43**

votes

**2**answers

966 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

**4**answers

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

**1**answer

523 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

**9**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**2**answers

899 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

**3**answers

473 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

**2**answers

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

**1**answer

520 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

**3**answers

455 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

**3**answers

396 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

**2**answers

602 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 ...

**8**

votes

**3**answers

802 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

**3**answers

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

**2**answers

259 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

**1**answer

546 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

**1**answer

214 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 ...

**8**

votes

**1**answer

412 views

+50

### 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,\\
...

**7**

votes

**2**answers

759 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

**2**answers

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

**0**answers

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

**4**answers

685 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

**3**answers

249 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

**4**answers

647 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

**2**answers

326 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

**2**answers

816 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

**1**answer

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

**0**answers

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

**2**answers

273 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 ...

**5**

votes

**5**answers

515 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

**3**answers

269 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

**3**answers

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

**1**answer

389 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

**2**answers

1k 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

**3**answers

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

**1**answer

588 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

**1**answer

122 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

**1**answer

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

**1**answer

595 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

**5**answers

627 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

**1**answer

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

**3**answers

676 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

**2**answers

199 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

**2**answers

86 views

### Number of edges in linklessly embeddable graphs

Consider graphs over $n$ nodes.
What is the maximum number of edges of a linklessly embeddable graph?
A more general question is the following. Given $\mu$ what is the maximum number of edges of ...

**4**

votes

**1**answer

210 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

**2**answers

463 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

**1**answer

219 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

**1**answer

267 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 ...