The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
18 views

Whether no local degeneracy in PLC implies edge-protection?

In a paper on Constrained Delaunay tetrahedralization (Meshing Piecewise linear complexes with Constrained Delaunay tetrahedralizations), in section 3, in proof of theorem 2, author claims that if ...
2
votes
0answers
99 views

How does part 5 of the paper “computational complexity of Minesweeper” work?

Marzio De Biasi mentioned this paper in this answer, and that paper's claim in part 5 would appear to resolve my question. However, there seems to be a significant gap in the proof. Even though one ...
3
votes
1answer
113 views

How to find the first $k$ points of high enough level using a priority search tree?

In reading Chan's paper, Closest Point Problems Simplified on a RAM, the following came up as a sub-problem: Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points ...
0
votes
0answers
53 views

Questions on “Improved Sketching of Hamming Distance with Error Correcting” by Porat and Lipsky

What is the proof of lemma 4.3 in this paper? http://u.cs.biu.ac.il/~porately/papers/submission_24.pdf That is, how does it follow from 4.1 and 4.2? Also, why is the constant 8 necessary? How is it ...
2
votes
0answers
113 views

Initial paper of the Moore Neighborhood algorithm

I don't exactly know if this is the place to ask it, but I'm looking for the original paper of the Moore Neighborhood algorithm. I need to make a reference to it (or whoever came up with it). I can't ...
8
votes
1answer
168 views

question about concurrent ZK paper by Prabhakaran & Sahai

Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity Page numbers are from the paper itself, and not the pdf. From page 3, "An interactive proof system is said to be black-box ...
6
votes
0answers
229 views

Can we reduce dimensions before applying high dimensional approximate nearest neighbor algorithms?

Andoni and Indyk presented a paper in FOCS 2006: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In this paper they present an algorithm for the $c$-approximate ...
9
votes
1answer
618 views

The Stalin compiler brutally optimizes, but how?

This question was first asked on Stackoverflow, but the question was closed and suggested that it should be moved to cstheory. Since compiler questions are quite rare here, I was not entirely sure. If ...
14
votes
2answers
286 views

Separation of a preprocessed polyhedron and a plane

I have serious trouble understanding one step in the paper of Dobkin and Kirkpatrick about the separation of polyhedra. I am trying to understand this version: ...