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
4 votes
1 answer
199 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 ...
usercsw's user avatar
  • 41
3 votes
1 answer
365 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 ...
Jake B.'s user avatar
  • 1,423
2 votes
1 answer
196 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 ...
rndm_ecn's user avatar
0 votes
0 answers
34 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 ...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
34 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 ...
simonp2207's user avatar
1 vote
0 answers
51 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 ...
user39430's user avatar
5 votes
2 answers
334 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 ...
yoyostein's user avatar
  • 1,219
-1 votes
1 answer
115 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 ...
Winnie_XP's user avatar
  • 287
2 votes
0 answers
67 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 ...
giulio bullsaver's user avatar
3 votes
0 answers
98 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 ...
giulio bullsaver's user avatar
5 votes
0 answers
81 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-...
Siddharth Bhat's user avatar
4 votes
2 answers
283 views

Software for finding conjugates in the braid group

The conjugacy problem for the braid group was solved by Garside, and gives an algorithm for determining whether two braids are conjugate. Since this algorithm is rather tedious, I was wondering if ...
user8253417's user avatar
12 votes
1 answer
373 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 = ...
Libli's user avatar
  • 7,210
1 vote
0 answers
26 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, ...
Manfred Weis's user avatar
  • 12.6k
4 votes
2 answers
209 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, ...
Manfred Weis's user avatar
  • 12.6k
1 vote
1 answer
132 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)=\...
James Cheung's user avatar
  • 1,855
3 votes
0 answers
81 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 ...
Dima Pasechnik's user avatar
1 vote
0 answers
69 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 ...
John Erbes's user avatar
3 votes
0 answers
131 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 ...
GWB's user avatar
  • 181
1 vote
0 answers
39 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 ...
tuna's user avatar
  • 523
4 votes
1 answer
202 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 ...
Till's user avatar
  • 469
1 vote
0 answers
49 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 ...
guest's user avatar
  • 11
2 votes
0 answers
71 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 ...
DCM's user avatar
  • 778
8 votes
1 answer
314 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$...
Taras Banakh's user avatar
  • 40.8k
4 votes
2 answers
777 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, ...
Smith's user avatar
  • 49
2 votes
1 answer
469 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. Based on this MathSE discussion, one can think of a method to get $\...
Nandakumar R's user avatar
  • 5,451
7 votes
1 answer
696 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 ...
Nandakumar R's user avatar
  • 5,451
5 votes
0 answers
84 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]$ ...
Lviv Scottish Book's user avatar
6 votes
1 answer
137 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 ...
Lviv Scottish Book's user avatar
2 votes
1 answer
145 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 ...
Leland's user avatar
  • 23
5 votes
3 answers
143 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 ...
Mauro Sox's user avatar
6 votes
1 answer
613 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 ...
Nandakumar R's user avatar
  • 5,451
1 vote
1 answer
98 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 $\...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
56 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 ...
Mohammad Al-Turkistany's user avatar
6 votes
0 answers
232 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 ...
Turbo's user avatar
  • 13.7k
2 votes
1 answer
203 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 ...
Alex Ozer's user avatar
  • 121
1 vote
0 answers
62 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 ...
Alina's user avatar
  • 11
16 votes
2 answers
275 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 ...
Anton Petrunin's user avatar
3 votes
1 answer
286 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\...
Samrat Mukhopadhyay's user avatar
1 vote
0 answers
48 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 ...
VS.'s user avatar
  • 1,816
1 vote
0 answers
59 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 ...
VS.'s user avatar
  • 1,816
1 vote
0 answers
64 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 ...
VS.'s user avatar
  • 1,816
2 votes
1 answer
399 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 ...
Sviatoslav Iakovlev's user avatar
2 votes
1 answer
251 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 ...
oren harlev's user avatar
2 votes
1 answer
107 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 |...
user avatar
5 votes
0 answers
349 views

Are nearby points in an algebraic curve necessarily connected?

I would like a result of the following form: For every algebraic curve $C$ in $\mathbb{R}\mathbf{P}^{n-1}$, there exists an explicit and easy-to-compute $\epsilon=\epsilon(C)>0$ such that ...
Dustin G. Mixon's user avatar
0 votes
0 answers
87 views

Why there isn't lexicographically smallest solution to a bounded linear program?

I am learning computational geometry when I run into this confusion. "A bounded 2D linear program may not have a lexicographically smallest solution", as the book says. I wonder why? I think we can ...
Yifu Luo's user avatar
4 votes
2 answers
127 views

Complexity of Determining the Edges of Planar Convex Hulls

Question: can the set of edges that resemble the convex hull ($CH$ for short) of $n$ points in the euclidean plane be determined in $O(n)$ time? I know that the time complexity of determining the $CH$...
Manfred Weis's user avatar
  • 12.6k
3 votes
0 answers
61 views

Biggest Cartesian Product Included in a Real Plane Curve

Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as ...
alpx's user avatar
  • 351
4 votes
2 answers
340 views

Complexity of Random Delaunay Triangulation in 3D

My question: Is the number of cells in a three-dimensional Poisson-Delaunay triangulation with $n$ vertices $\mathcal O(n)$ with probability one? which is equivalent to the question Is the ...
Dahn's user avatar
  • 141

1 2 3
4
5
10