# Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

507 questions
Filter by
Sorted by
Tagged with
18 views

### How to estimate the number of nodes in a trie based on a dictionary of words?

Say I want to build a trie out of 800,000 Sanskrit "base" words (in Devanagari script), with 20 prefixes and 2,000 possible suffixes. Each word is anywhere from 1-20 characters, and prefixes/...
1 vote
14 views

### How to avoid global delaunay check in conforming triangulation?

I implemented a conforming (i.e. it creates Steiner points using Ruppert's algorithm) delaunay triangulator, which is working, but there is one step I am doing that I straight up don't understand and ...
1 vote
26 views

### How to actually implement ruppert's algorithm?

I have been scouting the internet for resource son how to properly implement Ruppert's algorithm and what I ahve found is always lacking in details. The best resources I have so far are these 2: ...
1 vote
38 views

### Fast measurement of distance from point to mid segment?

Say you have a segment defined by 2 points $a,b$ and a third point $p$. You want to know the distance from $p$ to the midpoint of the edge. This is very straightforward: $$d = \|\frac{a + b}{2} - p\|$$...
1 vote
113 views

### Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time

I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to ...
1 vote
65 views

### Number of maximal induced trees in a connected planar graph

An induced subgraph $G’$ of a graph $G$ is a subset of its vertices along with all the edges that are present in $G$ among those vertices. For $G’$ to be a tree, all vertices of a cycle in $G$ cannot ...
91 views

### Are integer linear *feasibility* problems NP-hard?

I know that Integer Linear Programming problems are NP-hard. But it seems like this answer is only applicable to Integer Linear optimization problems. It seems like integer linear feasibility problems ...
24 views

### How to enforce convexity of triangulation output?

I implemented an incremental Delaunay triangulation algorithm. It basically works except it has this weird issue. The algorithm starts by creating a bounding triangle that it then splits recursively ...
1 vote
42 views

### product of every difference

Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo $10^9 + 7$ $$\prod_{i < j} (arr[j] - arr[i]) \% (10^9 + 7)$$ Best approach I can ...
20 views

126 views

### Algorithms for finding closest graph node within set of nodes

Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$? Furthermore, say we are doing many ...
43 views

### Need help proving the following for every integer n larger or equal to 1

i need help proving the following : $$\sum_{k=1}^{n}\frac{1}{(3k-1)(3k+2)}=\frac{n}{6n+4}$$ for every integer n larger or equal to 1 Can you help? Thanks
1 vote
46 views

### Distinguishing two distributions with f-divergence

The statistical distance (SD) has been widely used as a 'measure' of the closeness of two distributions $D_1$ and $D_1$. Suppose that the statistical distance (here, total variation with $\ell_1$ norm)...
1 vote