Questions tagged [computational-geometry]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
31 views

Placing a circle in a point cloud

I need to place a circle with fixed radius in a cloud of points. The circle also must lay in a polygon (the points are also in that polygon) This circle has to contain as many points as possible. Are ...
fanda's user avatar
  • 11
3 votes
0 answers
41 views

Affine point matching in general dimensions

Fix a positive integer $d$ and consider the $d$-dimensional Euclidean space $\mathbb{R}^d$. Let $S$ and $T$ finite subsets of $\mathbb{R}^d$ of the same size $n$. Under the assumption that $S$ and $T$ ...
rr314's user avatar
  • 131
2 votes
0 answers
84 views

Complexity of finding a room-partitioning

In a paper by Jack Edmonds and Laura Sanità (link: https://www.sciencedirect.com/science/article/pii/S1571065310001605) the following intriguing result is given: Given a triangulation $T$ of $3n$ ...
László Kozma's user avatar
3 votes
0 answers
83 views

Enforcing general position in $2d$ linear programming

Let $(x_1, y_1), ..., (x_k, y_k)$ be $n$ points in $\Re^2$. For my sake, $k=20$. I am trying to set up a linear program to find a set of $k$ points in the plane $P$ that satisfy some linear ...
user3508551's user avatar
  • 1,143
2 votes
0 answers
42 views

Geometric Set Cover Problem and Union Complexity

I have encountered an instance of the Geometric Set Cover problem where the complexity of the union of any subset with size, say k, of m objects is linear with respect to m. I am aware of a well-known ...
Arash Vaezi's user avatar
0 votes
0 answers
60 views

kd-tree optimality for orthogonal range search

It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
karmanaut's user avatar
  • 1,177
0 votes
0 answers
19 views

Intersection of cuttings with a new hyperplane in d dimensions

Consider a d dimensional space with $n$ hyperplanes in general position. Based on these hyperplanes $n/r$ cuttings are constructed. If a new hyperplane is given, how many of the $d$-simplices from the ...
Jarus's user avatar
  • 38
1 vote
1 answer
53 views

Enumerating part of an arrangement

Consider an arrangement of hyper-planes in $d$ dimensional space. Let us say the attributes are $\{A_1, A_2, \cdots, A_d\}$. If there was a constraint on say an attribute $A_i$ of the type $l_i \leq ...
Jarus's user avatar
  • 38
3 votes
1 answer
127 views

Is minimum knot crossing number elementary recursive?

One result in knot theory is that link crossing number is NP-hard. Another result is that the equivalence problem for knots and links is elementary recursive. So, given that the equivalence problem is ...
Niklas Rosencrantz's user avatar
3 votes
0 answers
27 views

Bound on line with minimum zone complexity in a line arrangement

In an arrangement of $n$ (pseudo)lines, the well known Zone Theorem gives a $O(n)$ bound on the complexity of the zone of any given line (for the purpose of this question, the complexity of the zone ...
Tassle's user avatar
  • 871
6 votes
1 answer
313 views

Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82

I was reading the paper "Optimal Algorithms for Approximate Clustering", Feder and Greene [1988] (https://dl.acm.org/doi/10.1145/62212.62255). Specifically, I was trying to look at the $1.82$...
Agile_Eagle's user avatar
0 votes
0 answers
23 views

Complexity of the vertices of a decomposed simple polygon to its cells

Given a simple polygon (without holes), consider a given decomposition of the polygon into convex sub-polygons. Suppose there are a number $m$ of convex sub-polygons and the number of the vertices of ...
Arash Vaezi's user avatar
2 votes
1 answer
308 views

VC dimension of the class of all polygons with k vertices

VC dimension of the class of convex polygons with $ k $ vertices is known to be $ 2k + 1$. For the general case I was able to derive a bound of the type $ O(k^2log(k)) $ (probably can be easily ...
Popescu Claudiu's user avatar
1 vote
0 answers
48 views

Partition points in the plane

Given $n=2k$ points in the plane and also given positive real value $r$. Is there an algorithm that partition points into two groups $G_1$ and $G_2$ such that each group contains exactly $k$ points ...
TAre's user avatar
  • 11
4 votes
1 answer
243 views

Binary Trees for Nearest Neighbor Search

Given points $x_1, ..., x_n \in \mathbb{R}^d$, consider a binary decision tree $T$ on $\mathbb{R}^d$ with $L$ leaves, i.e. for a point $y \in \mathbb{R}^d$ at every node of the tree, we check whether $...
Claudio Moneo's user avatar
5 votes
1 answer
107 views

Finding planes from their points

Given some points $P=\{x_1,\dots,x_m\}$ in a vector space $(Z/2Z)^n$, if $P$ is a union of linear subspaces all of the same dimension $1<d<n$, can we efficiently find these subspaces? (Any ...
Bjørn Kjos-Hanssen's user avatar
0 votes
0 answers
307 views

A problem in understanding an algorithm

I read a paper from John Hershberger with this title: "Minimizing the sum of diameters efficiently". That paper proposed a simple algorithm that finds a bipartition of points $S$ in the ...
ErroR's user avatar
  • 210
1 vote
0 answers
69 views

How can we prove what the shortest line between two points avoiding convex obstacles is? (visibility graphs)?

I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...
user49404's user avatar
  • 119
4 votes
0 answers
87 views

Complexity of detecting general position in the plane?

What is the complexity of detecting whether a given set of points in the plane is in general position? This surely must have been studied, but a quick search turns up nothing. For concreteness, let'...
Neal Young's user avatar
  • 10.1k
4 votes
1 answer
116 views

A counter example for the set mean objective

Let $\mathcal{P} = \{P_1, \cdots,P_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function \begin{align} cost(\mathcal{P},c) =...
Sudipta Roy's user avatar
0 votes
0 answers
74 views

"Fast" approximation algorithm for geometric hitting set of same-height rectangles

In the Geometric Hitting Set problem, we are given a set of $m$ geometric objects and a set of $n$ points in $\mathbb{R}^2$, and we wish to find a small subset of the points that hits all the objects. ...
Florent Foucaud's user avatar
2 votes
0 answers
34 views

Complexity of best folding of a 2D set (or how to optimize a sandwich)

Motivation: I was making lunch for my son, part of which is making a sandwich from two halves of a slice of bread. In order to minimize the parts of bread that have cheese on them, and are not covered ...
Shaull's user avatar
  • 5,571
0 votes
0 answers
99 views

How many maximal planar graphs are there?

We denote by a triangulation a (simple) maximal planar graph. How many triangulations on $n$ vertices are there? How many triangulations are there if we cannot distinguish the vertices, i.e. ...
John S's user avatar
  • 1
-2 votes
1 answer
188 views

How to calculate complexity in a high dimensional space?

Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong. For a specific f(), I'm defining a term '...
user2827214's user avatar
18 votes
0 answers
463 views

In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

Decision Problem Input: An $m$ by $n$ Boolean matrix $M$. Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left ...
Michael Wehar's user avatar
0 votes
0 answers
43 views

What is the best way to find circles that contain a given point (in 2D)?

Given $n$ circles all with radius $r$ and one point on a 2D plane, what is the best algorithm to find all circles that contain the given point. The circles and the point can change their positions. ...
Marc Grec's user avatar
  • 137
0 votes
1 answer
65 views

Find a boundary from set of 3d line segments

I have a set of n 3d line segments ...
YAKOVM's user avatar
  • 189
5 votes
1 answer
91 views

Complexity of computing the union of H-polytopes in three dimensions

Consider a set $P_1,\ldots,P_k$ of polytopes in $\mathbb{R}^3$, each given as an intersection of halfspaces with rational normals (in particular, they are all convex). We are also given a target ...
Shaull's user avatar
  • 5,571
1 vote
0 answers
44 views

Practical worst-case polylogarithmic dynamic orthogonal range queries?

There are a number of data structures in the literature that solve the dynamic orthogonal range search problem in polylogarithmic time (say, range trees). My understanding is that these structures ...
templatetypedef's user avatar
5 votes
0 answers
93 views

Optimal point placement on integer lattice

What is known about the following point placement problem? For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute \begin{eqnarray*} \mu_1(N,n)\triangleq\min_{\mathcal{P}\...
user56067's user avatar
-1 votes
1 answer
354 views

Example of Delaunay Triangulation where it does not minimize the maximum angle

I know that that the Delaunay triangulation maximizes the minimum angle of triangulation. And it does not minimize the maximum angle. If we consider the set of points in general position(no four ...
Inuyasha Yagami's user avatar
5 votes
0 answers
75 views

Computing 3D viewpoint of a set of non-intersecting segments

Consider the following problem: we are given a finite set of bounded line-segments in ${\mathbb R}^3$, and we want to decide whether there exists a point $p\in {\mathbb R}^3$ from which no two ...
Shaull's user avatar
  • 5,571
2 votes
1 answer
264 views

How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

Following this answer on MathOverflow and section 3 of the linked paper by David Eppstein on how to split an orthogonal polygon into rectangles I came to a point where I just fail to understand how to ...
Neonit's user avatar
  • 123
3 votes
1 answer
219 views

Convex polygons inclusion relation

I have the following problem which came as a subproblem in some work I was doing and I am completely stuck. Note that I am interested in it only in terms of worst case time complexity (not heuristics ...
ioannis's user avatar
  • 41
2 votes
1 answer
136 views

Data structures for embedded simplicial complexes

I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar ...
Will's user avatar
  • 215
1 vote
1 answer
170 views

The decision procedure of theory of closed real field is in NP-hard?

The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
XL _At_Here_There's user avatar
3 votes
1 answer
238 views

Minimal number of hyperplanes needed to separate sets of points from one other set

Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$. We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. ...
orlp's user avatar
  • 835
0 votes
0 answers
51 views

Volume computation of special polytopes

I'm interested in computing the volume of a special class of $\mathcal{H}$-polytopes and the complexity of doing so. I know that in general it is #P-hard to compute the volume of $\mathcal{H}$ -...
sqlman's user avatar
  • 11
4 votes
0 answers
55 views

$\ell_\infty$ partially enclosing ball problem

Suppose I have $n$ points in $\mathbb{R}^d$ endowed with the $\ell_\infty$ metric, and I wish to find a minimum-diameter ball that contains some $k$ of these points. What is known about this problem? ...
Aryeh's user avatar
  • 10.5k
1 vote
2 answers
114 views

Embedding a n-tree into a b-dimensional space

Given a (directed) n-tree $T=(N,E,r)$ rooted in $r\in N$, I want to represent each node $n\in N$ at most as a $m$-dimensional vector $v_n\in \mathbb{R}^m$ (From the current Yuri's reply, m cannot be $...
jackb's user avatar
  • 175
1 vote
0 answers
73 views

Mapping of entire balls using Locality Sensitive Hashing (LSH)

LSH functions are useful for approximate nearest neighbor search. They are usually defined, for distance metric $d$ and $c>1$ as follows: A family of hash functions is $(r, cr, p_1, p_2)$-LSH ...
R B's user avatar
  • 9,448
7 votes
1 answer
180 views

Reference request: Shortest homotopic curve via vertex releases

Let $C$ be a piecewise-linear path (or closed curve) in the plane, in the presence of polygonal obstacles. We would like to find the shortest path (or curve) homotopic to $C$. (A path $D$ is homotopic ...
Gabriel Nivasch's user avatar
0 votes
0 answers
33 views

Does optimal fitting flat must pass through the mean of the point set?

I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line. Project clustering is a natural generalization of k-...
Sudipta Roy's user avatar
3 votes
2 answers
161 views

Data structure for radial orderings of points on the plane

Assume points are always in general position. For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$. Consider shooting an ...
Chao Xu's user avatar
  • 4,399
3 votes
0 answers
75 views

Rearranging angles of a convex polyline to make it closed

Let {$\alpha_1, \alpha_2, ... ,\alpha_n$} be a string of n positive reals summing up to 2$\pi$. We inductively construct the following 2D polyline, denoting with $R[\alpha]$ the clockwise rotation by ...
Leonardo's user avatar
  • 181
1 vote
0 answers
107 views

LSH Probabilistic guarantees

A family $H$ is $(r,cr,p_1,p_2)$-sensitive if for all $x,y \in \mathbb{R}^d$ we have: $\lVert x-y\rVert <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, and $\lVert x-y\rVert > cr \quad \...
John B's user avatar
  • 21
3 votes
1 answer
478 views

Select circle with given radius that contains most points

Given some points on a coordinate system and some radius r, I need to place a circle with radius r somewhere on the coordinate system such that that circle includes the most points. I tried solving ...
user51847's user avatar
1 vote
0 answers
80 views

Points of a finite set wihtin a ball

I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$. In particular, I would like to be able to solve the problem of finding all the point ...
C.P.'s user avatar
  • 992
2 votes
1 answer
151 views

A least sized partition of a set under a distance metric

What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows: Input: A set $S=\{s_1,\ldots,s_n\}$, where the elements $s_i$ are ...
Lars Ericson's user avatar
5 votes
0 answers
70 views

Inapproximability Results for APX-hard Geometric Optimization Problems

A lot of Geometric Optimization problems are NP-hard and APX-hard to approximate (No PTAS unless P=NP). One example of the geometric set cover problem can be found here. However, it is not easy to ...
user avatar