Tagged Questions

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

2
votes
1answer
54 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
101 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
39 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
122 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
114 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
98 views

Checking smoothness of complex schemes by reduction to characteristic prime

Let $X=V(F_1,\ldots,F_n)$ be a closed subscheme of the complex projective space $\mathbb{P}^N_{\mathbb{C}}$ defined by homogeneous polynomials $F_i\in\mathbb{Z}[x_0,\ldots,x_N]$ with integer ...
0
votes
0answers
43 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
151 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
1answer
47 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
38 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
256 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
146 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
186 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 ...
6
votes
2answers
116 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
68 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
83 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
574 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
281 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
617 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
93 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
222 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 $$ ...
0
votes
0answers
33 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
3
votes
1answer
68 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 ...
0
votes
1answer
56 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 ...
4
votes
1answer
225 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
33 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 ...
0
votes
0answers
57 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
133 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
2answers
184 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$ ...
3
votes
1answer
70 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?
5
votes
3answers
283 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
1answer
125 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
183 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 ...
1
vote
1answer
230 views

Explicit computation of the action of a Dehn twist on the fundamental group of a surface

Let $S$ be a compact orientable surface of genus $g$. Now let $p\in S$ and $\gamma$ a closed simple curve on $S$ disjoint from $p$. It is not very difficult to compute the action of a Dehn twist along ...
1
vote
2answers
157 views

A Claim on Typical Voronoi Cells

I am trying to prove the following claim (may be it has been proven). Claim: Consider a set of points $\phi=\{x_1,x_2,...,x_i,...\}$ generated by a homogeneous PPP with rate $\lambda$ in the 2-D ...
3
votes
2answers
200 views

Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances

Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances. The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?
0
votes
0answers
94 views

minimizing the sum of euclidean norms with box constraints

minimizing the sum of euclidean norms with box constraints I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...
1
vote
0answers
44 views

Covering a set of points by bounded geometric object/objects

1) Let $S$ be a set of $n$ points in $R^d$. Now, given a bounded geometric object $G$, the problem is to check whether $S$ can be contained in $G$. 2) Also, in general setting, the problem is to ...
6
votes
0answers
76 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 ...
1
vote
1answer
63 views

Smoothly deforming a set of three-dimensional points

I want to deform a 3D mesh according to 3 or more control points, meaning that the transformation is constituted by pre-images $c_i$ and images $c_i'$ of these control points. Each point of the mesh ...
2
votes
2answers
174 views

Largest inscribed rectangle inside a convex polygon

It has been proved by Radziszewski in this paper K. Radziszewski. Sur une probleme extremal relatif aux gures inscrites et circonscrites aux gures convexes. Ann. Univ. Mariae Curie-Sklodowska, Sect. ...
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 ...
3
votes
1answer
167 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
0answers
226 views

Intuition behind minimizing the Dirichlet energy of a mapping

What does minimizing the Dirichlet energy of a mapping $\Phi$ achieve intuitively? Roughly it is the integral (or sum, if discrete) of $|\nabla \Phi(\;)|^2 dV$, with $V$ the volume. So is it, in some ...
4
votes
2answers
206 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 ...
3
votes
3answers
474 views

Intersection of Polyhedra

I'm writing a collision detection algorithm, and so far I've been using Joseph O'Rourke's book "Computational Geometry in C" as reference. It outlines an algorithm to determine whether a point is ...
1
vote
2answers
105 views

Incremental structure of a delaunay triangulation

This would probably be considered a reference request, as I would imagine it has been studied extensively in earlier work. Say I have a collection of distinct points $X = \{x_1,\dots,x_n\}$ in the ...
4
votes
1answer
237 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 ...
3
votes
2answers
427 views

Hyperrectangle partition of set of overlapping hyperrectangles

I have a set of $n$, $d$-dimensional hyperrectangles which may be overlapping in arbitrary ways. I would like to partition the area covered by this set into a set of non-overlapping hyperrectangles. ...
2
votes
1answer
314 views

Finding the vertices of a convex polyhedron from a set of planes

I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution. ...