Questions tagged [computational-geometry]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
98 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
39 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
21 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
89 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
53 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
51 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
34 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
62 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
50 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
32 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
60 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
48 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
71 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 ...
0
votes
1answer
32 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
36 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
70 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
56 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
31 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
127 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
84 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
80 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
30 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
43 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
67 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
88 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
14 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
47 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
93 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
158 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
73 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
vote
0answers
32 views

What are the correct steps in solving polygon monotone triangulation?

I am working out step by step and I am stuck on vertex 7. I got that it was a regular vertex and helper(e_i-1) is not a merge vertex so I look for the leftmost edge in the sweep line. My question is, ...
0
votes
0answers
38 views

When computing Monotone Polygon Triangulation, how do I store the formed diagonals in the DCEL?

It's my understanding that a DCEL have the following structs ...
2
votes
1answer
106 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 ...
4
votes
1answer
281 views

How to calculate the dimension of a convex polyhedron?

A convex polyhedron can be represented by a set of linear inequalities. If the inequalities involve $n$ variables, then the polyhedron can be $n$-dimensional, but it can also be of a smaller dimension ...
1
vote
2answers
52 views

Implementing piecewise linear functions

I need to implement piecewise linear functions (this is not homework, it is for my own personal project). However, I have been having difficulties to get it right. Below, I describe the ...
1
vote
0answers
67 views

Is it posssible to calculate the intersection area of rectangles with sweep Line and Interval or Segment Tree

I am curently working on automatic label placement, so for evaluating a model, one metric is to calculate the Area A: A is the sum of every part of a rectangle covered by another. So if two rectangle ...
1
vote
1answer
74 views

How does the sweep line algorithm check for intersection using vector cross product?

I am trying my best to understand the sweep-line algorithm to find line intersections. I have understood most of the intuition except how it is calculating the intersection between 2 line segments ...
4
votes
0answers
34 views

Is there a name for the class of distance functions that are compatible with k-d trees?

The typical nearest neighbor search implementation for k-d trees prunes branches when the distance between the target and the pivot along the current axis exceeds the smallest distance found so far. ...
5
votes
1answer
75 views

Maximize area of light with 4 light sources on a diagram of a room

Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized. Here is a simple ...
0
votes
0answers
38 views

Intersection of line segments induced by point sets from fixed geometry

I am reading up on algorithms and at the moment looking at the below problem from Jeff Erickson's book Algorithms. I solved (a) by seeing a relationship to the previous problem on computing the ...
0
votes
1answer
31 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 ...
1
vote
1answer
13 views

Clustering a set of point by affine transform

We are given a set of $n$ points on the plane $a_i = \{x^a_i, y^a_i\}$ and $b_i = \{x^b_i, y^b_i\}$. Assume that the points b are an affine transform of the points a, we can find a matrix $M$ and ...
2
votes
2answers
73 views

Is realization of unit disk graphs hard?

It is known that recognizing a unit disk graph is NP-hard [1]. However, the paper does not mention how hard the realization problem is. I have looked up several references [2][3][4]. None of the ...
2
votes
1answer
32 views

Euclidean geometry theorem proving complexity

Euclidean geometry is complete, so the problem of determining whether a statement $A$ is provable is computable. Do we know its time complexity?

1
2 3 4 5
14