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

0
votes
1answer
78 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 ...
22
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
272 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
74 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
22 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
88 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
56 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
204 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 ...
11
votes
1answer
281 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
194 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
210 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
4k 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
121 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
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 ...
2
votes
1answer
62 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
132 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
4k 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
217 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
643 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
122 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
198 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
138 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
44 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
87 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
406 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
813 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 ...
0
votes
1answer
265 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$. ...
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 ...
2
votes
0answers
170 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 ...
6
votes
2answers
119 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 ...
10
votes
1answer
609 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,\\ ...
0
votes
1answer
70 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
87 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, ...
5
votes
2answers
288 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
640 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
104 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
233 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 $$ ...
13
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$. ...
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
1answer
82 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 ...
4
votes
1answer
237 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 ...
3
votes
0answers
37 views

Find shift direction for min overlap area of 2 polygons

I have 2 arbitrary polygons (concave or convex) with certain overlap. Now there is some relative shift between these 2 polygons (vector s with a constant length). I want to find the direction of s ...
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 ...
3
votes
2answers
197 views

Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
0
votes
0answers
58 views

plotting parametrized algebraic curves near singularities

I have a parametrized algebraic curve: x(t)=A(t)/D(t); y(t)=B(t)/D(t); with A(t) and B(t) being polynomials in t. The curve is solution of a linear system in two unknowns x and y with Cramer's ...
3
votes
0answers
134 views

Dead Flies Problem [duplicate]

If a set of points in the plane contains one point in each convex region of area 1, then can it have finite density? what is the density of the points? In my understanding, it means the average ...
3
votes
1answer
75 views

Number of lattice polytopes contained in a given lattice polytope?

Given a (convex) lattice polytope, suppose we want to list or count all (convex) lattice polytopes (of the same dimension) contained in it. Are there efficient ways to do this?
4
votes
1answer
240 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 ...