4

Your algorithm is correct. The following is its proof of correctness. Let $S_1$ and $S_2$ be the optimal partitions of $S$. Let their medians be $m_1$ and $m_2$. Let the maximum element is $M$ that belongs to $S_1$ (without loss of generality). Let $m$ is the median of $S_1 \cup S_2 \setminus \{M\}$. Then, we can show that the value $M + m$ is at least $m_1+...


3

For each equivalence class $X$ of $R_1$, find the representatives of all elements of $X$ in $R_2$. This tells you how the elements of $X$ split in $R_1 \cap R_2$. (You might need to use some efficient data structures or algorithms beyond union-find.) Repeat for all other equivalence classes. Total running time is $\tilde{O}(n)$.


2

Yes, D*-lite is a directed graph algorithm, so it works fine with asymmetric edge weights by definition. However, note that the heuristic being admissible is not sufficient. According to the paper, it must be consistent. Based on what you described, I would guess Euclidean distance would be consistent for your graph, but we can't know for sure without ...


2

There are two ways this problem can be solved. I really like these solutions. Square Root Decomposition Keep a set of at most O(sqrtN) "active nodes". When you have a query of type 2, just loop through all these active nodes and add the distance between each one to the queried node. When you have a query of type 1, add the new node to the set if ...


1

The trivial solution concluded from the comments is as follows. Order (~$O(n\log{n})$) the given points as $P=[p_1,...,p_n]$, such that $$i < j \iff p_i < p_j$$. By iterating from $p_1$ to $p_n$ in $O(n^2)$ find all possible intervals of length 1 store them as a tuple of $(\text{subarray of points they contain}, \#\text{unique colors they contain})$. ...


1

You can use Clarkson's algorithm to find the smallest (non-degenerate) enclosing triangle in $O(d\log^2 n)$ expected time, where $d$ is the dimension of your input. So, for constant dimensions, it takes $O(\log^2 n)$ expected time. The algorithms is applicable, because the smallest triangle problem is an LP-type problem. Clarkson's algorithm has many ...


1

Instead of "subtract", it is easier to "try to avoid". Sort all edges first by their weights, then by whether they belong to $T$. In other words, for any two edge $e_1$ and $e_2$, $e_1$ precedes $e_2$ if and only if $w(e_1) \lt w(e_2)$, or $w(e_1) = w(e_2)$ and $e_1$ does not belong to $T$ and $e_2$ belongs to $T$ The above order can ...


1

The problem can be regarded as a special case of incidence reporting problem with $N$ unit circles and $N$ points in the plane. If the number of unit circles is $m$, then this problem can be solved in $\tilde{O}(m^2 + N)$ time ($\tilde{O}(\cdot)$ ignores polylogarithmic factors). First, explicitly computing the arrangement (the division of the plane, its ...


1

You may use a Well-Separated Pairs Decomposition (WSPD). This is a hierarchical decomposition, where at each level, you split the points into two parts, each of them a certain distance from the sphere enclosing the other set, and a certain radius of the sphere containing them. It runs in $O(n\log n + X)$, where $X$ is an output sensitive parameter, that ...


Only top voted, non community-wiki answers of a minimum length are eligible