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
0answers
30 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
75 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 ...
0
votes
0answers
28 views

Show that Delaunay triangulation contains Gabriel graph on a set of euclidean points

Let $P \in \mathbb{R} \times \mathbb{R}$ be a set of points on a euclidean plane. A Delaunay triangulation of $P$ is a graph $DT(P) = (P, E_{D})$ such that $\forall p, q, r \in P$, the edges $(p, q), (...
3
votes
1answer
55 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
59 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 ...
1
vote
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
51 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
103 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
39 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
57 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
36 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
31 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
73 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
106 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
55 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
31 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
48 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
55 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
37 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
67 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
55 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
33 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
49 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
27 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
37 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
47 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
80 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 ...
0
votes
1answer
66 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
vote
1answer
41 views

Determining the intersections of a line segment and grid

Problem: Given a line segment on the cartesian plane, determine where and which order it intersects a regular grid. This sounds simple, but is actually quite a tough problem. It's related to, but ...
5
votes
0answers
129 views

Finding the Hamiltonian cycle that uses the least amount of straight lines

How can i find the Hamiltonian cycle on an nxn grid that uses the least amount of stright lines (curves left/right as much as possible)? Here's an example we have devised for 8x8: Here is an example ...
6
votes
1answer
85 views

Number of vertices and edges lies on the boundary of bounded cells in line arrangement

I am learning computational geometry by myself using these lecture notes from ETH Zurich. Here is an exercise (8.9) I have been stuck for a few days: For a line arrangement $A$ of a set of $n$ lines ...
0
votes
0answers
81 views

I think I've found a flaw in this paper: On finding a minimal enclosing parallelogram. Can someone verify it for me?

On finding a minimal enclosing parallelogram I think the problem will occur when we only consider the first clockwise antipodal vertex. I think instead we should consider an edge when there are two ...
1
vote
0answers
31 views

An algorithm to split an area into multiple polygons based on other polygons intersection

I have a list of n polygons (A,B,C,D,E,...) which possibly intersect each other. I need to find a new list of polygons (or multi-...
2
votes
1answer
46 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 ...
6
votes
1answer
68 views

Closest point in embedded simplicial complex

Suppose I have a simplicial $k$-complex $\mathcal S$ whose vertices are embedded in Euclidean space $\mathbb R^n$, for roughly $k< n\leq 6$. Examples include triangle mesh surfaces ($k=2$) embedded ...
3
votes
2answers
95 views

Finding closest edge to a point in a planar graph

I have a point location problem (in a planar graph) with a twist: rather then finding which region the point is located in, I would like to find the closest segment (edge) to a point, ideally with a <...
1
vote
0answers
15 views

Ear-clipping algorithm for non-planar polygons

I was looking into the ear-clipping algorithm for triangulating simple polygons. I have successfully implemented it on planar polygons. However if polygon is non-planar the algorithm breaks down. ...
2
votes
1answer
48 views

Sort half-edges around common vertex in 3d

I'm trying to figure out this problem for very long time and am no getting nowhere. I'm working on a simple 3d modeler that uses half-edge data structure. Say I have non-manifold geometry where two ...
1
vote
0answers
50 views

Convex hull on set of squares

Imagine a set of two to six squares within 3D-space. The goal is to generate a convex hull around these squares as efficiently as possible. The following constraints are known: Each of the two to six ...
3
votes
1answer
95 views

Maximal subsets of a point set which fit in a unit disk

Suppose that there are a set $P$ of $n$ points on the plane, and let $P_1, \dots, P_k$ be distinct subsets of $P$ such that all points in $P_i$ fits inside one unit disk for all $i$, $1\le i\le k$. ...
4
votes
1answer
103 views

minimum travel from point to point with incremental steps

It's my first time to make a question here. I have a curious problem about algorithm, in the center of Cartesian plane (0,0) I need to go to another point (x,y) -x and y are belong to Z numbers - but ...
5
votes
3answers
172 views

Usefulness of Differential Geometry

I recently came across these books: Differential Geometry and Lie Groups: A Computational Perspective Differential Geometry and Lie Groups: A Second Course Their subject matter really intrigues me, ...
2
votes
0answers
75 views

Enumerating points on the integer lattice, within a sphere, sorted by angle, in O(1) space

Inspired by this StackOverflow question: https://stackoverflow.com/questions/63346135 (it was not clearly presented, and got closed) Let's say I wanted to enumerate all the 3D points on the integer ...

1
2 3 4 5
14