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
0answers
27 views

Uniqueness of Riemann Constant Vector Solution

Let $X$ be a compact, genus $g$ Riemann surface (given as the desingularization and compactification of a plane algebraic curve), $J(X)$ its Jacobian, and $A : X \to J(X)$ the Abel map $$A(P) = ...
2
votes
1answer
54 views

Maximal opening angle of a polygon from a point [on hold]

I'm looking for an algorithm that given a 2D convex polygon and point outside it, returns the two points of the polygon which are the two extremities of the polygon when viewed from that point. One ...
2
votes
1answer
74 views

The circle with minimal radius covering known finite set of points on a plane

Given some points on a plane, how to determine the circle with minimal radius covering all these points?
5
votes
2answers
195 views

Do computational geometers use Lagrange multipliers?

Can anyone point me to an example of a problem that (more or less) originated in computational geometry whose solution requires the use of Lagrange multipliers (or Kuhn-Tucker conditions, or dual ...
0
votes
1answer
46 views

Detect perimetral edges of a polygon [closed]

I'm developing a building editor. Users can draw rooms by adding angles (vertices of the room) with a left click. Clicking on an existing angle closes the room and fills the floor by using the ...
3
votes
1answer
111 views

Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position. Let $T$ be a triangulation of $S$, (somehow) selected uniformly at random from all triangulations of $S$. (There are an ...
1
vote
0answers
51 views

Epsilon-net of operator norm ball around Identity

Suppose I look at the set of matrices which are invertible and satisfy $$ \left\|A-Id\right\|_{op}<r $$ for some $r<1$, where $Id$ is the $n\times n$ identity matrix. An $\epsilon$-net of such ...
4
votes
2answers
64 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
123 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 ...
4
votes
2answers
244 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
259 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 ...
4
votes
2answers
92 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 ...
5
votes
1answer
133 views

Algorithm that generates a n-simplex that cover n-polytope?

Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?
3
votes
1answer
140 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 ...
10
votes
0answers
141 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 ...
9
votes
3answers
700 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 ...
2
votes
0answers
87 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 ...
2
votes
0answers
111 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
44 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 ...
6
votes
1answer
130 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
88 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 ...
0
votes
2answers
299 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 ...
1
vote
0answers
28 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
59 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. ...
0
votes
1answer
97 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 ...
2
votes
1answer
418 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 ...
1
vote
2answers
240 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 ...
14
votes
1answer
332 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 ...
7
votes
0answers
129 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
1answer
79 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
158 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
0answers
51 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 ...
2
votes
1answer
154 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$) ...
0
votes
1answer
131 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
0answers
158 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 ...
0
votes
2answers
389 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 ...
3
votes
2answers
101 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
42 views

Non-Convex Polygons with “Antipodal Visibility”

by "antipodal visibility" of planar, simple polygons I mean the following property: if two points $p$ and $q$ on the polygon's boundary divide the polygon's boundary into two polylines of equal ...
0
votes
1answer
280 views

Is there a Gröbner basis analogue that exists for vector spaces?

Suppose I have a coordinate system $t_1,\ldots t_N$ with a lexicographical ordering. Let LT denote choosing the lowest term of a polynomial with respect to this ordering. e.g. LT$(t_1 + t_2)=t_2$. ...
2
votes
0answers
188 views

Dissection of a polygon into convex polygons

Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons. I would be very grateful for any information on this problem. Remark 1. There ...
8
votes
1answer
263 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 ...
7
votes
2answers
138 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 ...
0
votes
1answer
73 views

Paper on unit disk graphs

I was wondering if anybody knows of a 'link' to the paper by Marathe 1995 et al on analysis of the greedy algorithm for finding a Max independent set in Unit Disk Graphs?
2
votes
2answers
91 views

Complexity of Untwisting Polygons

What is the complexity of the following task: given a sequence $p_1, ..., p_n, p_1$ that defines a closed polyline in the euclidean plane, what is the complexity of finding a reordering of the points, ...
10
votes
1answer
669 views

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,\\ ...
5
votes
2answers
296 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 ...
8
votes
2answers
664 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 ...
2
votes
1answer
116 views

Computable link invariants

I am interested in the following situation: given a braid $B$, it induces a link $L$ in a pretty straightforward way ("glue" the endpoints, like here). For a braid $B$, we know how to represent it in ...
2
votes
1answer
245 views

Hilbert function of points in $\mathrm{P}^2$

Let $\Gamma$ be a collection of $d$ points in $\mathrm{P}^2$, and $I$ the graded ideal of $\Gamma$.If $$ ...
3
votes
1answer
95 views

Finding a minimum covering of a polygon with interesting shapes

After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of ...