Skip to main content

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.

34 questions from the last 365 days
Filter by
Sorted by
Tagged with
1 vote
0 answers
68 views

To partition a triangle into $n$ convex pieces with sum of number of sides over all pieces maximized

This post is a variant on To cut a triangle into $n$ $p$-sided polygonal regions. Question: Given a positive integer $n$, a triangular region is to be cut into $n$ convex pieces so that the sum over ...
Nandakumar R's user avatar
  • 5,979
0 votes
0 answers
72 views

Reflections of Voronoi diagrams

I wonder if something similar to the following fact is known, and I would greatly appreciate any references. Let $t_1, t_2, \ldots, t_N$ be unit vectors in $\mathbb{R}^n$. Let $S$ denote the unit ...
Cozy's user avatar
  • 1
1 vote
0 answers
37 views

Computing all roots of a function with square-root terms

Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function $$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$ Can we find all the ...
Abheek Ghosh's user avatar
0 votes
0 answers
37 views

Constructing a minimum-volume outer approximation polytope with fewer facets

I am tackling the following problem: Given a set of points $D \in \mathbb{R}^d$ and their convex hull, represented with $n$ facets, I want to construct a convex polytope $P$ with at most $m<n$ ...
Shperb's user avatar
  • 101
0 votes
0 answers
25 views

Is there a name for a spanner graph that only considers distance to a root node?

A $t$-spanner graph of a set of points $\{p_i\}$ in the plane is a graph $G = (V, E)$ such that for any pair of vertices $p_i, p_j \in V$, the shortest path distance $d_G(p_i, p_j)$ in $G$ is at most $...
Tom Solberg's user avatar
  • 4,049
1 vote
0 answers
58 views

On partitioning the surface of a convex solid into geodesically convex equal area regions

We refer to a subset S of the surface of a convex solid C as geodesically convex if the shortest path along the surface of C joining any two points in S lies entirely within S (and if there are more ...
Nandakumar R's user avatar
  • 5,979
1 vote
0 answers
13 views

Complexity of counting maximal points in query orthogonal rectangles

The problem stated in the title is the following: given an $n\times n$ binary matrix $M=\left(m_{rc}\right)$ report the number of $1$'s in a query rectangle $[i,j]\times[h,k]$ $1\le i\lt j\le n,\, 1\...
Manfred Weis's user avatar
  • 13.2k
4 votes
1 answer
356 views

Left and right halves of convex curve

Let $S$ be a set of $n$ points in the plane in general position (no 3 on a line), $n$ even. A halving line is a line through $2$ points of $S$ that partitions $S$ into 2 equal parts ($(n-2)/2$ points ...
Xd00fg's user avatar
  • 214
1 vote
0 answers
22 views

Calculating an optimal scaling factor for Delaunay triangulations

consider a finite set $\mathcal{P}(x,y)=\lbrace(x_1,y_1),\dots,\,(x_n,y_n)\rbrace$ of points in the Euclidean plane and let $\mathrm{DT}(x,y)$ be the Delaunay triangulation of $\mathcal{P}(x,y)$ ...
Manfred Weis's user avatar
  • 13.2k
3 votes
1 answer
130 views

Why is the Vietoris–Rips complex $\operatorname{VR}(S, \epsilon)$ a subset of the Čech complex $\operatorname{Čech}(S, \epsilon\sqrt{2})$?

$\DeclareMathOperator\Cech{Čech}\DeclareMathOperator\VR{VR}$I am reading Fasy, Lecci, Rinaldo, Wasserman, Balakrishnan, and Singh - Confidence sets for persistence diagrams (see here for a version of ...
Kindness Chen's user avatar
9 votes
0 answers
205 views

Placing triangles around a central triangle: Optimal Strategy?

This question has gone for a while without an answer on MSE (despite a bounty that came and went) so I am now cross-posting it here, on MO, in the hope that someone may have an idea about how to ...
Benjamin Dickman's user avatar
3 votes
1 answer
431 views

Detecting a PL sphere and decompositions

Question 1. A PL $n$-sphere is a pure simplicial complex that is a triangulation of the $n$-sphere. I'm looking for a computer algorithm that gives a Yes/No answer to whether a given simplicial ...
Uzu Lim's user avatar
  • 903
1 vote
1 answer
103 views

Algorithm to find largest planar section of a convex polyhedral solid

We add a bit more on shadows and planar sections following On a pair of solids with both corresponding maximal planar sections and shadows having equal area . We consider only polyhedrons. Given a ...
Nandakumar R's user avatar
  • 5,979
1 vote
1 answer
134 views

An algorithm to arrange max number of copies of a polygon around and touching another polygon

A related post: To place copies of a planar convex region such that number of 'contacts' among them is maximized Basic question: Given two convex polygonal regions P and Q, to arrange the max ...
Nandakumar R's user avatar
  • 5,979
1 vote
0 answers
142 views

Explicit computation of Čech-cohomology of coherent sheaves on $\mathbb{P}^n_A$

$\newcommand{\proj}[1]{\operatorname{proj}(#1)} \newcommand{\PSP}{\mathbb{P}}$These days I noticed the following result of (constructive) commutative algebra, which I think is probably well known ...
Jürgen Böhm's user avatar
5 votes
0 answers
475 views

Closest vertices of an AABB to a ray in n-dimensions

I came across this computational geometry problem and have not been able to find a satisfactory solution for it. A ray is known to originate from within an n-dimensional hypercube (AABB) in any ...
Ood's user avatar
  • 81
1 vote
1 answer
178 views

Inside-out dissections of solids -2

We record some general questions based on Inside-out dissections of solids Inside-out dissections of a cube Can every convex polyhedral solid be inside-out dissected to a congruent polyhedral solid?...
Nandakumar R's user avatar
  • 5,979
3 votes
0 answers
83 views

Practical way of computing bitangent lines of a quartic (using computers)

Are there known practical algorithms or methods to calculate the bitangent lines of a quartic defined by $f(u,v,t)=0$ in terms of the 15 coefficients? Theoretically you can set up $f(u,v,-au-bv)=(k_0u^...
fp1's user avatar
  • 101
1 vote
0 answers
93 views

Inside-out dissections of a cube

Ref: Inside-out polygonal dissections Inside-out dissections of solids Definitions: A polygon P has an inside-out dissection into another polygon P' if P′ is congruent to P, and the perimeter of P ...
Nandakumar R's user avatar
  • 5,979
5 votes
1 answer
269 views

Is the maximal packing density of identical circles in a circle always an algebraic number?

There is a lot of interest in the maximal density of equal circle packing in a circle. And I thought that knowing whether or not the solution is always algebraic or not would be useful. My original ...
Teg Louis's user avatar
1 vote
1 answer
104 views

Finding the point within a convex n-gon that minimizes the largest angle subtended there by an edge of the n-gon

This post records a variant to the question asked in this post: Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon Given a convex n-gon, ...
Nandakumar R's user avatar
  • 5,979
6 votes
2 answers
189 views

Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon

For any point P in the interior of a convex polygon, the sum of the angles subtended by the edges of the polygon is obviously 2π. Given a convex polygon, how does one algorithmically find the point (...
Nandakumar R's user avatar
  • 5,979
0 votes
0 answers
32 views

Set of enclosed convex polyhedra in a graph

Given a straight-line graph embedded in $\mathbb{R}^3$ with known vertex coordinates and edges and no edge intersections, is it possible to find all the enclosed convex polyhedra inside? If so, is ...
n1ps's user avatar
  • 1
1 vote
0 answers
96 views

An algorithm to decide whether a convex polygon can be cut into 2 mutually congruent pieces

This post is based on the answer to this question: A claim on partitioning a convex planar region into congruent pieces A perfect congruent partition of a planar region is a partition of it with no ...
Nandakumar R's user avatar
  • 5,979
1 vote
0 answers
65 views

Algorithm to generate configurations with kissing number 12

That the kissing number of a sphere in dimension 3 is 12 is well known. However, it is also known that there is a lot of empty space between the 12 spheres. I deduce (am I wrong?) that there are many ...
GRquanti's user avatar
  • 111
0 votes
0 answers
65 views

Computational tasks resulting from Chern-Weil theory

I have recently learned Chern-Weil theory for smooth and complex manifolds, as well as surrounding material on cohomology with integral coefficients. I am curious what computational tasks are ...
user avatar
1 vote
1 answer
68 views

To maximize the volume of the polyhedron resulting from perimeter-halvings of a convex polygonal region

We add one more bit to Forming paper bags that can 'trap' 3D regions of max surface area (note: some possibly open related questions are also in the comments following the answer to above ...
Nandakumar R's user avatar
  • 5,979
1 vote
0 answers
91 views

A claim on the largest area circular segment that can be drawn inside a planar convex region

This post adds a little to To find the longest circular arc that can lie inside a given convex polygon A circular segment is formed by a chord of a circle and the line segment connecting its endpoints....
Nandakumar R's user avatar
  • 5,979
0 votes
0 answers
67 views

Comparing partitions of a given planar convex region into pieces with equal diameter and pieces of equal width

We continue from Cutting convex regions into equal diameter and equal least width pieces. There we had asked for algorithms to partition a planar convex polygon into (1) $n$ convex pieces of equal ...
Nandakumar R's user avatar
  • 5,979
1 vote
0 answers
91 views

Dissection of polygons into triangles with least number of intermediate pieces

This wiki article: https://en.wikipedia.org/wiki/Wallace%E2%80%93Bolyai%E2%80%93Gerwien_theorem shows the dissection of a square into a triangle via 4 intermediate pieces. It appears easy to form a ...
Nandakumar R's user avatar
  • 5,979
3 votes
0 answers
85 views

Computational complexity of exact computation of the doubling dimension

Given a finite metric space $X$, the doubling constant of $X$ is the smallest integer $k$ such that any ball of arbitrary radius $r$ can be covered by at most $k$ balls of radius $r/2$. The doubling ...
pyridoxal_trigeminus's user avatar
1 vote
0 answers
41 views

Are there rectangles that can be cut into non-right triangles that are pair-wise similar and pair-wise non-congruent?

We generalize the questions of Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent? Can any rectangle be cut into some finite number of triangles that ...
Nandakumar R's user avatar
  • 5,979
1 vote
0 answers
92 views

Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?

We add a bit to Tiling the plane with pair-wise non-congruent and mutually similar triangles and Cutting polygons into mutually similar and non-congruent pieces A (non square) rectangle can obviously ...
Nandakumar R's user avatar
  • 5,979
0 votes
1 answer
75 views

Robustness of doubling dimension to small perturbations

Let $M$ be a metric space. Then the doubling dimension of $M$, denoted $\dim M$, is defined to be the minimum value $k$ such that every ball in $M$ of radius $r$ can be covered by at most $2^k$ balls ...
pyridoxal_trigeminus's user avatar