We just launched a new product: Collectives on Stack Overflow. How do they work? Listen to learn more.

Questions tagged [computational-geometry]

Questions about algorithmic solutions of geometric problems, or other algorithms making usage of geometry.

Filter by
Sorted by
Tagged with
-4
votes
0answers
22 views
0
votes
0answers
12 views

Calculating the shortest vector between a vector and a truncated cone

I am trying to understand a certain implementation of calculating the shortest vector between a vector and a truncated cone in 3D. The original idea is introduced in this paper. So if we have two ...
0
votes
1answer
19 views

Nearest Neighbour search with Kirkpatrick's Hierarchy and Re-Triangulating Delaunay after vertex removal

Ok, so I'm having bit of an issue understanding nearest neighbour search with delaunay triangulation. In particular, how do I re-triangulate my delaunay triangulations once I introduced holes? But I ...
2
votes
1answer
44 views

Difference between convex hull algorithms

I was wondering what are the main differences in terms of efficiency of convex hull algorithms? Brute force algorithm is inefficient due to iterating over every three vertices in our set and its time ...
0
votes
1answer
13 views

Finding the distance from a point to a $R^m$ restricted area in $R^n$

The problem is described below: When m=2 and n=3, it is basically finding the distance between a point and a line segment in $R^3$. But when both m and n are larger, do I have to use a generic ...
0
votes
0answers
15 views

How does the railway model of computation get translated to motion on the heptagrid tiling of the hyperbolic plane?

I have been reading these, along with slowly chipping away at the two books Margenstern has produced: A universal cellular automaton in the hyperbolic plane A Universal Cellular Automaton on the ...
0
votes
1answer
4k views

Divide and Conquer Algorithm for Hidden Line Removal

You are given n nonvertical lines in the plane, labeled $L_1, ..., L_n$, with the $i^{th}$ line specified by the equation $y = a_i x + b_i$. We will make the assumption that no three of the lines ...
0
votes
2answers
59 views

Find the largest rectangle inscribed in a region partitionable into rectangles

Given a rectilinear polygon, what is an run-time efficient algorithm that finds the largest inscribed rectangle the sides of which either parallel or perpendicular to the sides of the rectilinear ...
2
votes
0answers
24 views

Finishing at rest at a target in 2d space

I asked a similar question here, except I forgot to specify that the final velocity must be 0. I have 2 points in 2D space, start = $s$ and target = $t$, and a starting velocity $v_0$. At each time ...
1
vote
1answer
18 views

Vector pathing via acceleration with velocity

I'm trying to solve a scenario where I need to find the smallest number of time steps to reach a location in 2d space, where I can manipulate the velocity with an acceleration at each time step where ...
3
votes
0answers
43 views

Find the largest interior rectangle composed of partitioning rectangles

Suppose a rectangle $R$ is partitioned into more than one smaller rectangles of positive area. What is the fastest algorithm to find the largest rectangle strictly within the all-enclosing rectangle $...
0
votes
0answers
43 views

Find coordinates of points when distance is known amongst them

Lets say I have 6 point name A, B, C, D, E, F. Distance between a point and it's nearest 3-4 points are known i.e the displacement. Now I want to assign x and ...
5
votes
1answer
43 views

Computing the set of points nearest to a point in a polygon boundary

Let $P$ be a polygon. For each point $x$ on the boundary of $P$, denote by $N_P(x)$ the set of points in $P$, that are nearer to $x$ than to any other point on the boundary of $P$. Given a subset $X$ ...
1
vote
1answer
47 views

How to find simple polygons in a complex polygon created by two lines

Given the image attached, I am looking for a way/strategy/pseudocode to iteratively find each polygon created either by two blue-dotted line segments, a blue-dotted line segment and an intersection, ...
2
votes
1answer
82 views

Algorithm to construct a parabola that hits a given target and avoids given boundaries

I'm working on a video game and I'm struggling with the math behind one of the enemies. The enemy is a grenade launcher mounted on a vertical rail, which can slide up and down, and lob a grenade at ...
0
votes
0answers
37 views

Classification of a box relative to a line algorithm

I'm having trouble understanding the correctness of the following algorithm: why is the choice of the $p_n$ coordinates correct? Also, in figure 3.8 $n$ is pointing left and up, so according to figure ...
0
votes
1answer
35 views

Finding lowest point in circles

Given n disks in the plane, i want to compute the lowest point in their intersection area, im looking for a simple randomized incremental algorithm. There are some circles in the plane, these circles ...
1
vote
1answer
94 views

Description of shape in a vector form

I would like to ask for references to algorithms that can project shape information about an object to 1 dimension. Specifically I am training a neural network to be able to identify objects with ...
4
votes
1answer
355 views

Computing the right tangent of two convex hulls

My question deals with the algorithm of computing the convex hull in 2D by Preparata. Let us assume we have two sets, $A$, $B$, of points in the plane. Let $CH(A)$ and $CH(B)$, denote the convex ...
2
votes
1answer
113 views

Calculate the area of the shape created by multiple paths

I'm trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example: Basics 4 separate paths (A,B,C,D) which are a collection of ...
1
vote
1answer
104 views

How to determine if 2 rays intersect?

We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a ...
3
votes
0answers
59 views

How to check whether a lattice polytope embeds into another lattice polytope?

Suppose I have two polytopes $P\subset \mathbb R^m$ and $Q\subset \mathbb R^n$ with vertices with integral coordinates. How do I check whether $P$ is embeddable into $Q$? More precisely, "...
3
votes
0answers
31 views

A simple algorithm to solve the MST Sensitivity Analysis problem in linear time when the MST is a path

The problem. Given an undirected, connected, edge-weighted graph $G=(V, E_G; w)$ and a minimum spanning tree (MST) $T=(V, E_T)$ of $G$, the MST sensitivity analysis problem asks to find, for each ...
1
vote
1answer
91 views

Upper and lower tangent line to convex hull from a point

Is it possible to find an upper and lower tangent line to a convex hull in $log(n)$ time where $n$ is number of points on a convex hull? I have just done it in linear time where I checked for upper ...
3
votes
1answer
747 views

3D gift wrapping algorithm: how to find the first face in the convex hull?

I am implementing the gift wrapping algorithm to find the convex hull of a set of points in the 3D space. However, all the articles I have read seem to omit the description of the first step of the ...
3
votes
2answers
124 views

Finding all pairs of points with no point in between

Suppose there are $n$ points $p_1,p_2,\dots,p_n$ with color red or blue on a line. We want to find all pairs $(p_i,p_j)$ whose color is distinct and such that there are no points between them. If ...
1
vote
1answer
252 views

Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
3
votes
1answer
62 views

Minimum-area enclosing equilateral triangle for a point set

We have $n$ points $P$ in $2D$ space. We want to find an enclosing equilateral triangle $\Delta$ with minimum area in $O(n\log n)$. Suppose We know that at least on side of $\Delta$ covers at least ...
2
votes
1answer
105 views

Maximize length of side of triangle from points on a circle

Given a circle with $n$ points, among all triangles we can make using these points, we want to find a triangle with maximum length of its shortest side in $o(n^2)$. We try to make a relation between ...
7
votes
3answers
2k views

If a point is a vertex of convex hull

The exercise is Given a set of point $S$ and a point $p$. Decide in $O(n)$ time if $p$ is a vertex of convex polygon formed from points of $S$. The problem is I am a little bit confused with ...
3
votes
1answer
269 views

Number of double wedges containing a point

We have a set of $n$ double wedges on a plane. (By double wedge, I mean two lines intersecting at a point, with opposite sides of the point considered as "inside" the double wedge.) Now ...
4
votes
0answers
62 views

Number of permutations with satisfactory triangles

We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
3
votes
1answer
175 views

Data structure to query intersection of a line and a set of line segments

We want to pre-process a set $S$ of $n$ line segments into a data structure, such that we can answer some queries: Given a query line $l$, report how many line segments in $S$ does it intersect. It ...
0
votes
1answer
48 views

Closest Pair of Points Algorithm - Fortune and Hopcroft

I am interested in implemented the deterministic ${O(n\log(\log(n)))}$ algorithm for the closest pair of points problem described here by Fortune and Hopcroft: https://ecommons.cornell.edu/bitstream/...
2
votes
0answers
60 views

Checking if a given point is convex hull vertex [duplicate]

I have a problem in computational geometry: Given $n$ point in 2D space,and given a point $P$, design an algorithm check that whether $P$ is a vertex of convex hull or not in $O(n)$. My idea 1: I ...
0
votes
1answer
32 views

Scaling down a set of points into a smaller area

A visibility graph $G(P) = (V,E)$ of a set $P = \{p_1, \dots, p_n\}$ of points is defined as follows. Each vertex $u \in V$ corresponds to a point $p_u \in P$. There exists an edge $uv \in E$ if, and ...
5
votes
0answers
36 views

Efficient algorithm to compute the Heesch number of a shape

The Heesch number of a shape is the maximum number of layers of copies of the same shape that can surround it. For example the following shape (in the center) has a Heesch number of 4, because we can ...
9
votes
2answers
250 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their stable, ...
0
votes
0answers
55 views

Finding minimum distance between two convex polygon

We have two disjoint convex polygon $P,Q$, each with size $n$ , how we can find minimum distance between two convex polygon $O(\log n)$? We think for each points in $P,Q$ we must check to find ...
10
votes
4answers
794 views

Recovering a point embedding from a graph with edges weighted by point distance

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
6
votes
2answers
1k views

Turning a simple polygon with holes into exterior-bounded only

I am converting cartographic objects, which have an exterior boundary (simple polygon) and zero or more interior boundaries (also simple), into a less sophisticated format that specifies exterior ...
1
vote
1answer
41 views

Finding closest line segment intersecting rays

Assuming we have a fixed set of line segments $S$ such that any two segments are either disjoint or have a common endpoint. A query would look like this; given a query point $q$ shoot 4 rays from $q$ (...
2
votes
1answer
58 views

Find out if a path exists avoiding circular obstacles

Given a rectangle defined by its corners $(0, 0)$ and $(w,h)$, $n$ circles $\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ with the same radius $r$, I need to determine the smallest possible radius r ...
0
votes
1answer
188 views

Formal definition of loss surface of multi-layered networks

Let $\mathcal{L}$ be a loss function associated with a multi-layered neural network. So it seems almost everyone in AI/ML community is interested in the Hessian $H=\partial^2 \mathcal{L}$ of $\...
1
vote
0answers
34 views

Count number of intervals containing a point

There is a problem (10.6) in Computational Geometry: Algorithms and Applications 2.edition by de Berg et al. where you have to solve the problem of given $n$ intervals, $I$, on the real line, count ...
4
votes
1answer
44 views

Can we find the largest intersecting subfamily of convex polygons in quadratic time?

Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (...
4
votes
0answers
74 views

Approximation Algorithms via Unit Disk Graph Embeddings

A unit disk graph is defined by a collection of $n$ vertices corresponding to $n$ points on the plane, with an edge between any two vertices whose distance is at most $r$. Some $NP$-hard problems ...
0
votes
1answer
89 views

Concentric convex hulls

Given N points in a 2D plane, if we start at a given point and start including points in a set ordered by their distance from the starting point. After including every point, we check if there is a ...
4
votes
2answers
4k views

Fast algorithm for interpolating data from polar coordinates to cartesian coordinates

I have a set of solution nodes generated over a polar grid. I would like to convert / interpolate these solution nodes onto a Cartesian grid: That is, using the image above, for each node in the ...
2
votes
1answer
59 views

Better way to decide if a set is a pure simplicial complex

Setup I am trying to write a function that determines if a set of vertices, edges and faces is a pure simplicial complex. A pure simplicial complex is a set where all facets have the same degree, a ...

1
2 3 4 5
15