Questions tagged [computational-geometry]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
15 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
40 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
12 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
14 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 ...
2
votes
0answers
23 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
17 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 ...
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 ...
3
votes
0answers
41 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
42 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
46 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
34 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 ...
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
89 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
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 ...
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 ...
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(...
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 ...
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
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 ...
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 ...
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
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/...
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
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 ...
2
votes
1answer
114 views

Efficient algorithm to compute the diameter of a convex set?

Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set? It is possible to do it efficiently for a set of points, but imagine that the ...
1
vote
0answers
43 views

Finding all integer points on a hypersurface

Given a function $f$ of $n$ variables, is there a reasonable way to generate all integer points on the hypersurface given by $f(x)=0$? To be more specific, let us assume that $f$ is a polynomial with ...
0
votes
0answers
22 views

Packing a sphere with cuboids

This question on the Mathematics SE addresses how to pack a sphere with unit cubes. This addresses how to pack a 2D grid with rectangles. We can pack a sphere with the minimum number of unit cubes $m$ ...
3
votes
2answers
90 views

High dimensional Pareto dominance query data structure

I have a large (10 million+) set $X$ of data points in some high dimensional $\mathbb{R}^d$ ($d \geq 500$) space. Each data point is quite sparse, e.g. has around $10$ components. Every missing ...
2
votes
0answers
17 views

Use a directed graph to express a high-dimensional orthogonal polyhedra

I have a set of $d$-dimensional hyper-rectangles with integer axes. These hyper-rectangles may overlap. The union of these hyper-rectangles forms a $d$-dimensional orthogonal polyhedra $P$. I sort the ...
1
vote
1answer
56 views

Finding “entrance” points in a set of d-dimensional points. Can I do better than O(N^2)?

I am given a set of d-dimensional points, and need to find the set of entrance points in them. Definitions: A point p1 captures p2 if 1) All dimensions of p1 is smaller or equal to p2; and 2) At ...
2
votes
1answer
35 views

Which graph partitioning algorithm can solve this problem?

In brief: Here I have a cyclic graph above. I want to partition the graph vertices into 3 clusters. (With the mindset of cluster-wise "load balancing") ...
2
votes
0answers
52 views

Mahalanobis distance of point to plane algorithm

I am trying to understand the Mahalanobis distance of a point from the plane given by this paper. The algorithm is given below: Calculate covariance of point $S_{uu}$ Apply a whitening transform to ...
4
votes
1answer
61 views

Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?

I am approaching a problem where, among other things, I will have to repeatedly check if a point is within a (set of) polygon(s) in the 2D plane. the polygons are either convex or star-shaped with a ...
3
votes
1answer
41 views

For two sets of points find if second one is result of linear transformation of the first

Say we have two sets of points in vector-2 space (In actuality need to solve this problem in vector-3 space but decided to start with a simpler problem). The points in the second set are the result of ...
3
votes
1answer
69 views

Trapezoidal decomposition of a graph

When we plan the motion of a robot we may apply the trapezoidal decomposition of free space. While applying the trapezoidal decomposition we add nodes to both the centers of trapezoids and vertical ...
3
votes
1answer
63 views

Mapping spherical coordinates onto faces of an icosahedron

I'm looking for an algorithm which takes spherical coordinates (say lat-long) and identifies which face of an icosahedron a ray moving in that direction would intersect. My end goal here is to explore ...
1
vote
0answers
35 views

Transition from Delaunay triangulation to Voronoi diagram

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any ...
1
vote
0answers
61 views

Can we make at most 3 comparisons in the closest points algorithm instead of 7?

Let's say I am using the divide and conquer algorithm outlined here, but I only want to return the minimum distance. I understand why that algorithm puts an upper-bound at 7 but I think that can be ...
1
vote
1answer
50 views

How can the local feature size become arbitrarily small?

I am stuck at the following exericse: Let $\rho$ denote the local feature size. Draw an example where the curve C contains the line segment from $(-1, 0)$ to $(1, 0)$, but where $\rho( (0,0) )$ is ...
1
vote
0answers
28 views

Show that the local feature size is Lipschitz continuous

In class we defined "local features size" $\rho$ as follows: Let $C$ be a smooth closed curve in the plane, and let $x$ be a point of $C$. The local feature size $\rho(x)$ of $x$ is the ...
1
vote
0answers
74 views

Trapezoidal Map and Search Tree

i am studying on trapezoidal maps. In the last section, "Analysis" of this paper, it says "The expected query time is indeed O(log n). Again the search structure size can be quadratic ...
1
vote
1answer
53 views

minimum number of points a convex hull must have

Quick question: Say for example there are 10 colinear points. my question is does a convex hull have to be a convex polygon? or can it be a line as well according to the formal definition of the ...
0
votes
0answers
54 views

Creating Priority Search Tree bottom up from a Complete Binary Search tree in O(n)

I have a Complete Binary Search Tree of points ordered(sorted) on the y-axis (such that the point with the mid y of all the points is the root and its left children have decreasing y from the root and ...
1
vote
1answer
104 views

Is Dual Graph of a Triangulation of a Polygon Tree?

I have read that; if a polygon contains a hole in it, then the dual graph of a triangulation of the polygon not have to be a tree. But could not get it exactly. How is it possible, what is the ...
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 ...

1
2 3 4 5
15