Questions tagged [computational-geometry]

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.

Filter by
Sorted by
Tagged with
2
votes
1answer
62 views

Existence of solutions of polynomials systems (and their “rough” shape) over $\mathbb{R}$ & friends with positive-dimensional ideals

This is a follow-up (but self-contained) question to my previous one. There I asked about state-of-the-art methods to solve multivariate polynomials systems over non-algebraically closed fields in ...
0
votes
0answers
73 views

On some optimal containers of a set of points on the 2D plane

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find the smallest semicircular region (semidisk) that contains the points the smallest ...
0
votes
0answers
34 views

Finite element method reference, from the perspective of the finite elements themselves

I found the finite element chapters in The Finite Element Method of Elliptic Problems especially enlightening and would like to learn more about the theory behind the base components of a general ...
4
votes
1answer
111 views

$\varepsilon$-net of a $d$-dimensional unit ball formed by power set of $V = \{+1, 0 -1\}^d$

I have a set of $d$-dimensional vectors $V = \{+1, 0, -1\}^d $. Then $P(V)$ constitutes the power set of $V$. I now construct a set of unit vectors $V_{\mathrm{sum}}$ from the power set $P(V)$ such ...
2
votes
1answer
110 views

Implementation of Koebe–Andreev–Thurston circle packing?

The circle packing theorem (Koebe–Andreev–Thurston theorem) claims for a planar graph, we can pack disjoint circles, such that: the circles correspond to vertices and the disks are tangent if the ...
2
votes
1answer
58 views

Discrete curve-shortening flow – numerical implementation

I need to investigate the properties of open curves which evolve according to the standard curve-shortening flow (Wikipedia link), but with fixed extremes as boundaries (si it should converge to the ...
0
votes
0answers
25 views

Restrictions on crossing edges in Delaunay triangulations

what can be said about crossing edges in Delaunay triangulations, i.e. about pairs of edges that constitute to the heaviest perfect matching int the $K_4$ induced by the quadruplet of adjacent ...
0
votes
0answers
13 views

Defining planar geometric shape hulls via graph connectivity

A fundamental problem in Computational Geometry is to generalize convex hulls to simple polygons that partition a given finite set $\boldsymbol{P}$ into two sets $\boldsymbol{C}$ of corners and $\...
0
votes
0answers
21 views

Bipartite Euclidean matching: Statistics of a random edge?

In a bipartite Euclidean matching, see e.g. this thesis (and the corresponding diagram below), two point processes, denoted $B$ and $S$, drawn from a Euclidean space $\mathbb{T}$ (a torus with flat ...
1
vote
0answers
30 views

How do I find the portion of a cell/voxel lying within a defined surface?

We have a 3-dimensional grid of voxels (or cells), with individual voxels being of volume $dx\,dy\,dz$ where $dx=dy=dz=1$. A cone-like surface is defined by some function, $z = f(x, y)$, which in ...
1
vote
0answers
33 views

fast V representation update of polytope

Say that I have both the V and the H representation of a (possibly unbounded) polytope $P$. I want to append a some rows to the H representation, how can I quickly update the V representation to ...
4
votes
2answers
182 views

Is there an upper bound on the number of points in point cloud for which we compute the persistent homology?

I am interested in the topic of persistent homology (topological data analysis). According to what I read, there is some roadblock in the analysis of "big data" using persistent homology as it is ...
0
votes
0answers
19 views

VC Dimension of a range space of (X,ΔR) where (X,R) is of vc dimension d

I have a question: Let (X , F) be a range space of bounded VC-dimension D. Show that the range space (X , ΔF), where ΔF = {SΔS' | S, S' ∈ F} (and Δ denotes the symmetric set difference) has VC-...
0
votes
1answer
92 views

IntersectInP bug of Macaulay2 [closed]

I am trying to use the intersectInP command in Macaulay2, inside package ReesAlgebra. However, I tried to follow the exact code in the user-guide, but it doesn't run in my Ubuntu app (of win 10). Can ...
2
votes
0answers
39 views

grobner basis of an ideal dependent on some parameter

Suppose $I = \langle f_1, ... , f_l \rangle$ is an ideal generated by polynomials $f \in k[x_1,\dots,x_n]$, where $k$ is a field of rational functions in some parameters $s_1,\dots,s_m$. What are the ...
1
vote
0answers
41 views

finding a good term order for grobner basis

What are the tricks to pick a "good" monomial order to find a Grobner basis for a given ideal? By good I mean one in which the final Grobner basis has a simple expression in terms of the ...
5
votes
0answers
52 views

special classes of ideals (eg. toric) that admit faster Buchberger algorithm?

I have heard that toric ideals allow one to speed up the Buchberger algorithm considerably (see Grobner bases of toric ideals, Remark 2,3). My question is two-fold: What are the precise complexity-...
8
votes
0answers
157 views

Characteristic polynomial of an $8 \times 8$ symmetric matrix with indeterminate entries related to octonionic multiplication

I consider $1,i,j,k,l,m,n,o$ the standard basis of the (complexified if you like) octonions ($\mathbb{O}$ for the octonions). Let $a = x_1.1 +\ldots + x_8.o$, $b = x_9.1+ \ldots + x_{16}.o$ and $c = ...
1
vote
0answers
22 views

Complexity of tour-expansion heuristic for the planar Euclidean TSP

This is a followup question to this one: Computational Geometric Aspects of Greedy Tour Expansion. Assume that the candidate point, whose insertion into current incurs the least tour-length increase, ...
4
votes
2answers
145 views

Algorithm for reporting all triangles with unique interior point

What is known about the complexity of and/or practical algorithms for reporting all triplets of points from finite set of at least four points of which no three are collinear in the Euclidean plane, ...
0
votes
1answer
67 views

Existence of element $(x_0,y)$ in a set of common zeros for all $(x_0,y)$ satisfying system of inequalities

Let $f_1,f_2,\cdots,f_n,g_1,g_2\cdots,g_m\in \mathbb{R}[x,y]$, then define the affine variety and semi-affine variety as follows: $V(f_1,f_2,\cdots,f_n):=\{(x,y)\in\mathbb{C}^2: f_1(x,y)=f_2(x,y)=\...
3
votes
0answers
48 views

Signed triangulations of simplicial polyhedra

Let $\partial S$ be the boundary of a compact polyhedron $S\subset\mathbb{R}^3$, assumed to be generic, in the sense that every face of $S$ is a triangle, and so that there are exactly two triangles ...
1
vote
0answers
61 views

Is there a workable numerical method for determining the center of a circle through three points? [closed]

I'm a 73-year-old engineer struggling with numerically implementing a math problem. I am working on a kinematic linkage project that generates motion paths (as long sequences of x,y coordinates) of ...
3
votes
0answers
108 views

Lower bound on the intersection of $\ell_1$ $n$-balls

Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ in $\ell_1$ norm, with distance $d$ and radius $R$. Is there a lower bound on the volume of the intersection between the two n-balls? (assuming the ...
1
vote
0answers
26 views

Vertex enumeration for polytope with a sparse halfplane description?

Say I have a (bounded convex) polytope $P\subset\mathbb R^d$ with description $Ax\le b$, where $A$ is sparse in the sense that there are at most $k$ nonzero entries in each row or column, where $k$ is ...
3
votes
1answer
128 views

Reference: Packing under translation is in NP

I am looking for a reference for a result that I am aware of. Let me describe the result. Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP time, if $p_1,\ldots,p_n$ can be ...
1
vote
0answers
47 views

How does one translate from convex hull to a set of facets (inequalities)? [duplicate]

Suppose I have defined a convex set as the convex hull of a set of points. (I know that all these points are "extremal points" of the convex set.) I know want to translate this description of the ...
2
votes
0answers
63 views

Software recommendation request: deciding whether a system of polynomial equations is solvable by radicals

The following system of equations comes from a very simple geometric figure I have to deal with a lot at work. Here $r_0,r_1,r_2$ and $L$ are known parameters, and the $x_i$s are the coordinates I'm ...
3
votes
1answer
162 views

What is the form of the $(v_0,v_1)$-pizza curve?

Assume that there are two (competing) pizza houses situated at the points $0$ and $1$ on the complex plane. These pizza houses can deliver pizza to points of the plane with the largest velocities $v_0$...
4
votes
2answers
409 views

Convex hull in a discrete space [closed]

I know some algorithms which compute the convex hull in a continuous space. Are there efficient algorithms to compute it in a discrete domain? For example in 3D discrete space, given the blue points, ...
1
vote
1answer
188 views

Partitioning polygons into acute isosceles triangles

Question: Given an $N$-vertex polygon (not necessarily convex). It is to be cut into the least number of acute isosceles triangles. Remarks: Based on this MathSE discussion, one can think of a ...
7
votes
1answer
396 views

To minimize the Hausdorff distance between convex polygonal regions

Definition: The Hausdorff distance is the greatest of all the distances from a point in one set to the closest point in the other set. Question: Given two convex polygonal regions P1 and P2 on the ...
4
votes
0answers
70 views

Problem to efficiently compute the Volume of $d$ anchored 4D cuboids

An easy still unsolved special case of Klee's measure problem with applications in multiple objective optimization is described in the following. Let $[\vec a_1,\vec b_1],\dots,[\vec a_n,\vec b_n]$ ...
6
votes
1answer
113 views

Minimizing the number of segments in drawings of planar graphs

Every planar graph has at most $3n-6$ edges, where $n$ is the number of vertices. Moreover, every planar graph can be drawn with straight-line edges in the plane, without crossings. For example, for ...
2
votes
1answer
83 views

Given a set of $n$ points in $[0,1)^d$, how do I partition the space into hyperrectangles such that each hyperrectangle contains exactly one point?

I'm new to this forum so I apologize if my question is ill-posed or too general. I have the following problem. Given a set of $n$ points in the unit hypercube, $[0,1)^d$, how can I partition the unit ...
5
votes
3answers
126 views

Fast computation of a ball with radius r with largest number of input points

We are given a set S of n points equipped with some metric and an integer $r>0$. We define $B(x,r) \subseteq S$ (the ball with radius r centered in x) to be the set of points in S within distance r ...
5
votes
1answer
257 views

On covering convex 2D regions with rectangles

Given a convex 2D region $C$ and a positive integer $N$. We need to cover $C$ with $N$ rectangles such that the sum of the areas of the $N$ rectangles is the least – no further constraints on the ...
1
vote
1answer
89 views

Estimating volume of a simple object

Volume computation is $\#P$ hard. Take the $[0,1]^n$ polytope. Slice it by an half space inequality with $poly(n)$ bit rational coefficients into two unequal halves. Volume of bigger section is $\...
2
votes
0answers
42 views

Complexity of existence of simple polygonalization with prescribed area?

This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
6
votes
0answers
194 views

Complexity of scissors congruence?

Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with ...
2
votes
1answer
100 views

Intersection of sphere with triangle containing moving vertices

First off, apologies if I cannot properly articulate my question in the most formal way. However, I believe my question should be simple enough to grasp anyhow. In $\mathbb{R}^3$, I would like to ...
1
vote
0answers
55 views

Projection of a polytope along 4 orthogonal axes

Consider the following problem: Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
16
votes
2answers
264 views

Finding a plane numerically

Suppose I have three large finite sets $\{x_i\}$, $\{y_i\}$ and $\{z_i\}$; they are obtained by measuring coordinates of a collection of vectors in $\mathbb{R}^3$, but I do not know which triples ...
3
votes
1answer
258 views

How to find the vertices of the set $\{v_i\in \mathbb{R}:a_1\ge v_1\ge v_2\ge \cdots\ge v_n\ge 0,\ q_2\le \sum_{i=1}^n p_iv_i\le q_1\}$

I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, $q_2\le \sum_{i=1}^n p_iv_i\le q_1$, with $\{p_i\}_{i=1}^n,\ q_1,q_2$ positive reals, and only one bound for the coordinates: $v_1\...
1
vote
0answers
44 views

Efficient scissors congruence between efficiently describable convex polytopes and simplex?

Is there a convex polytope in $\mathbb R^n$ describable by only $O(poly(\log n))$ half-plane inequalities with positive volume (so at least $n+1$ vertices) such that the standard simplex has a ...
1
vote
0answers
35 views

Covering a simplex efficiently by efficiently describable polytopes?

Take a standard simplex or cube in $\mathbb R^n$. Is there a way to cover it with $O(poly(\log n))$ convex polytopes each describable by only $O(poly(\log n))$ half-plane inequalities? If not what ...
1
vote
0answers
59 views

Polytopes that can be efficiently described and efficiently covered by cubes or simplices?

Is there a bounded convex polytope $\mathcal P\subseteq\mathbb R^n$ with $m$ vertices, whose vertex vectors span $\mathbb R^n$ (so $m$ is $\Omega(n)$) and just $O(poly(\log n))$ half-plane ...
2
votes
1answer
122 views

Build reversed No-Fit-Polygon

I need some robust algorithm to optimally fit one non-convex polygon into another. The destination one can contain holes. Recently I found scholarly articles on this subject: One of them describes ...
2
votes
1answer
127 views

Algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane

I am trying to find an algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane, with a total of $n$ vertices. Let $h$ denote the number of vertices on ...
2
votes
1answer
86 views

A questions concerning Laguerre/Voronoi tessellations

Fix $n>1$ distinguished points $x_1,\ldots, x_n\in \mathbb R^d$, the Voronoi tessellations are the subsets $V_1,\ldots V_n\subset\mathbb R^d$ defined by $$V_k~~ := ~~ \big\{x\in\mathbb R^d:\quad |...

1
2 3 4 5
7