Pith. sign in

REVIEW 2 major objections 5 minor 41 references

Dynamic Unit-Disk Range Reporting

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A dynamic unit-disk range reporting data structure answers each query in $O(\log n + k)$ time, matching the static optimum while keeping previous space and update bounds.

desk verdict Genuine query-time improvement plus a reusable arc shallow cutting; one unproved transfer lemma is the load-bearing risk. read the letter →

arxiv 2501.00120 v1 pith:U7OGCNLV submitted 2024-12-30 cs.CG cs.DS

Haitao Wang , Yiming Zhao This is my paper · ORCID
classification cs.CGcs.DS MSC 68U0568P05
keywords unit-diskrangereportingdynamicdatastructuresshallowcuttingscirculararcsemptinessalpha-hullsfractionalcascadingconformingcoverage
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that dynamic unit-disk range reporting—maintaining a moving set of points so that a query disk of fixed radius can list all points inside it—can be answered in $O(\log n + k)$ time, where $k$ is the number of reported points. The previous best dynamic structure took $O(\log^2 n / \log\log n + k)$ per query; the new query time matches the best known static structures and is therefore optimal up to constant factors. The improvement does not change the space or update costs: $O(n\log n)$ space, $O(\log^{3+\epsilon} n)$ amortized insertion, and $O(\log^{5+\epsilon} n)$ amortized deletion. The engine is a new shallow-cutting algorithm for equal-radius circular arcs, which the authors also use to give a simpler static structure and to speed up dynamic unit-disk emptiness queries to $O(\log n)$ per query with $O(\log^{1+\epsilon} n)$ updates. If correct, the result closes the gap between dynamic and static query performance for the fixed-radius neighbor problem.

What carries the argument

The load-bearing object is a shallow cutting for circular arcs: a family of bottom-open pseudo-trapezoid cells, each bounded by two vertical rays, a top edge that is an equal-radius arc or an axis segment, and no bottom boundary, such that every cell intersects at most $K$ arcs and the cells cover the region of depth at most $k$. The paper computes such cuttings in $O(n\log(n/k))$ time by first building a vertex-segment form $(Q,S)$, where $Q$ is a set of sample points below the $x$-axis and $S$ is a set of disjoint segments on the axis whose vertical decomposition covers the shallow region. The bridge between forms is the line-separated $\alpha$-hull, defined as the complement of all unit disks with centers above the axis that contain none of $Q$; its vertical decomposition yields the pseudo-trapezoid cells. This arc cutting is then substituted into the known dynamic hierarchy for line reporting, whose interval trees over $x$-projections and deletion-only conflict lists answer $k$-lowest-arcs queries in $O(k + \log n)$ time.

What would settle it

Run the paper's arc shallow-cutting algorithm on an adversarial set of unit arcs, for example many arcs with nearly coincident endpoints on the $x$-axis, and verify the claimed per-cell bound: if any bottom-open pseudo-trapezoid cell from the vertex-segment decomposition intersects more than $3K$ arcs, then Observation 4, hence Lemma 11 and Theorem 2, fails. A second check is whether a $k$-lowest-arcs query using the lemma's interval trees ever misses an arc that should be among the $k$ lowest at the query vertical line.

Watch

Extended reading notes

Core claim

The central claim is that the line-based machinery for dynamic halfspace range reporting can be re-derived for equal-radius circular arcs: replace the shallow cutting of lines with a new shallow cutting of unit arcs, and the whole hierarchy carries over. The paper proves the arc cutting exists with an $O(n\log(n/k))$-time construction, first in a vertex-segment form built from line-separated $\alpha$-hulls, then converted into bottom-open pseudo-trapezoid form. Lemma 8 asserts that the fully dynamic collection of shallow cuttings inherits the earlier line-based guarantees, which yields $k$-lowest-arcs queries in $O(k + \log n)$; Observation 2 converts those into arc-below-point reporting, and the conforming coverage grid (Lemma 2) reduces each unit-disk query to $O(1)$ line-separable instances. The claimed consequence is Theorem 1: $O(n\log n)$ space, $O(\log^{3+\epsilon} n)$ insertions, $O(\log^{5+\epsilon} n)$ deletions, and $O(\log n + k)$ queries. A byproduct is a static structure with the same query bound built from elementary techniques, and a dynamic emptiness structure with $O(n)$ space, $O(\log^{1+\epsilon} n)$ updates, and $O(\log n)$ queries.

Load-bearing premise

The whole result rests on the assumption that a standard dynamic construction for finding the lowest lines at a vertical line carries over unchanged to equal-radius circular arcs once the line-cutting subroutine is replaced by an arc-cutting subroutine; the paper asserts this inheritance in a single sentence, so if arcs misbehave at any step, the claimed query bound collapses.

Editorial extensions

If this is right

  • Unit-disk range reporting queries now take optimal $O(\log n + k)$ time in a dynamic setting, matching the static data structure and removing the previous log-factor gap.
  • Dynamic unit-disk range emptiness drops to $O(\log n)$ query time with $O(\log^{1+\epsilon} n)$ amortized updates in $O(n)$ space, improving over the previous $O(\log^2 n)$ query and $O(\log^4 n)$ deletion costs.
  • The static UDRR structure achieves $O(n)$ space, $O(n\log n)$ preprocessing, and $O(\log n + k)$ queries using elementary techniques, offering a simpler alternative to the 3D halfspace-lifting route.
  • The arc shallow-cutting algorithm is a reusable primitive: any problem that reduces to reporting arcs below a point, or to $k$-lowest-arcs queries among equal-radius arcs, can adopt the same cutting and inherit its bounds.
  • Insertions remain at $O(\log^{3+\epsilon} n)$ and deletions at $O(\log^{5+\epsilon} n)$ amortized time, so the query speedup does not trade off update performance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the line-to-arc transfer in Lemma 8 is sound, the same strategy should apply to other dynamic queries over equal-radius arcs, such as fixed-radius nearest-neighbor or disk-containment problems, yielding query times closer to their static bounds.
  • The dynamic conforming coverage grid (Lemma 2) is a standalone primitive: any unit-disk problem that needs to touch only $O(1)$ cells per query could reuse it, independent of the arc shallow cutting.
  • A natural stress test is to instantiate Theorem 2 on adversarial arc arrangements, such as many arcs crossing near a common vertical line, and measure whether cell conflict lists stay within the proved $3K$ bound; unexpected violations would point to where the single-sentence inheritance argument needs care.
  • The static structure's use of fractional cascading hints that a pointer-machine variant with the same $O(\log n + k)$ query bound may exist, since fractional cascading is usually a RAM-oriented device; whether the bound survives on a pointer machine is not addressed by the paper.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies dynamic unit-disk range reporting: maintain a set P of n points under insertions and deletions so that all points inside a query unit disk can be reported. The main claimed result (Theorem 1) is an O(n log n)-space structure with O(log^{3+eps} n) amortized insertion, O(log^{5+eps} n) amortized deletion, and optimal O(log n + k) query time, improving the previous query bound of O(log^2 n / log log n + k). The method reduces the problem to dynamic line-separable unit-disk reporting, then to dynamic k-lowest-arcs queries over a set of x-monotone unit-circular arcs. The main new technical ingredient is a shallow cutting algorithm for such arcs (Theorem 2, proved in Section 6 with a detailed charging argument). The dynamic k-lowest-arcs structure (Lemma 4) is obtained by adapting the shallow-cutting hierarchy of Chan and de Berg--Staals for lines/planes; the key transfer is Lemma 8, whose proof is a one-paragraph assertion that the line-based hierarchy carries over once the line cutting routine is replaced by the authors' arc cutting routine. The paper also gives a simpler static O(log n + k) unit-disk reporting structure and improved dynamic unit-disk emptiness queries.

Significance. If the main dynamic claim is correct, it is a significant result: it is the first dynamic unit-disk range reporting structure with optimal O(log n + k) query time while preserving the previous update bounds. The static construction, though matching the known optimal bounds of Afshani--Chan, is genuinely simpler and uses elementary tools. The shallow cutting algorithm for circular arcs is developed in detail, with a careful size proof, and is likely to be useful independently. The dynamic emptiness byproduct is also an improvement over the previous nearest-neighbor-based bounds. The paper is not circular: epsilon, b, and r are asymptotic balancing parameters rather than fitted constants. However, the central dynamic theorem rests on Lemma 8, and that lemma is not proved in the manuscript; this is the main weakness.

major comments (2)
  1. [Section 5.2.2, Lemma 8] Lemma 8 is the load-bearing transfer from the line/plane dynamic shallow-cutting hierarchy to the arc setting, and its proof is a single paragraph: it states that Lemma 8 follows from [11, Theorem 3.1] with the improvement of [12], and that 'we replace their shallow cutting algorithm by ours in Theorem 2 for Γ. Everything else is the same.' This is not a proof of the four stated properties. The line-based hierarchy uses cuttings that cover the whole plane and whose cells are unbounded trapezoids meeting every vertical line; the arc cuttings of Theorem 2 are shallow cuttings covering only the (<=k)-level, with bottom-open pseudo-trapezoid cells, and the statement later in the query description that 'the x-projections of T_i^j partition the x-axis into intervals' is not justified for such shallow cuttings. The proof also does not explain how the rebuilding schedule, the interval trees over x-projections, the deletion-only conflict lists, or property (3) -- the guarantee that every candidate arc appears in some list queried at level i_k -- survive the replacement. Since Theorem 4, Lemma 4, and hence Theorem 1 inherit their query and update bounds from Lemma 8, this missing argument is a genuine gap, not a presentation issue. The authors should supply a complete proof of Lemma 8, or state and prove an explicit arc-specific version of the dynamic hierarchy.
  2. [Section 5.2.1, Lemma 7] Lemma 7 is likewise asserted by analogy: it is said to be 'obtained by following the same algorithmic scheme as [7, Lemma 6] and replacing their shallow cutting algorithm for lines with our shallow cutting algorithm for arcs of Γ in Theorem 2.' This lemma is used in the second case of the proof of Lemma 4, for conflict lists of size m < log^3 n, and it is needed to obtain the final O(log n + k) query bound. The same concerns as for Lemma 8 apply: the deletion-only structure in [7, Lemma 6] relies on specific properties of cuttings of planes, and the manuscript does not verify that those properties transfer to bottom-open pseudo-trapezoid shallow cuttings for bounded x-monotone arcs. Lemma 7 should either be proved or replaced by an argument that does not depend on an unverified transfer.
minor comments (5)
  1. [Section 3, first paragraph] There is a typographical error in 'F orming a grid G'; it should read 'Forming a grid G'.
  2. [Section 7.1, Lemma 14 proof] The proof of Lemma 14 states the inequality x(b_i) <= x(b_{i+1}) twice; the second occurrence should presumably be x(a_i) <= x(a_{i+1}), since the goal is to compare the centers via both endpoint orders.
  3. [Section 5.2.2, case 2] In the second case of the query-time analysis, the text says 'Since m < log^3 m'; this should be 'm < log^3 n'.
  4. [Section 6.3, Step (3) of Theorem 3 proof] In the removal step, the line 'As discussed in the proof of Lemma 10, Δ ⊆ H_ℓ({q1,q2})' appears to refer to the cell σ of the epsilon cutting, not the cell Δ of VD(Q_IN,S_IN); the notation should be corrected for readability.
  5. [Section 5.2.2, heading] The heading 'F ully-dynamic data structure for Lemma 4' contains a spurious space; it should read 'Fully dynamic data structure for Lemma 4'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main derivation rests on a new arc shallow-cutting algorithm and external dynamic-hierarchy results, not on its own output.

full rationale

Walking the derivation chain from Theorem 1 back to the paper's own inputs shows no step equates the target bound with a fitted parameter or with the authors' earlier theorem by definition. Theorem 1 reduces the query to Lemma 3 via the conforming coverage Lemma 2; Lemma 3 reduces to the k-lowest-arcs structure Lemma 4 and Observation 2. Lemma 4 is built from Theorem 2, the new arc shallow-cutting algorithm, whose proof in Section 6 is self-contained and independent of dynamic unit-disk range reporting. The dynamic-hierarchy Lemma 8 is imported from Chan [10-12] and de Berg-Staals [7]; its proof is only a one-sentence 'replace their shallow cutting algorithm by ours... everything else is the same' (Section 5.2.2). This is an unverified transfer and a genuine correctness risk, but it is not circular: no property in Lemma 8 is defined in terms of the lemma itself or of the query bound being proved; it is an analogy to an external theorem, not a self-definition. The paper's self-citations (Lemma 1 and Lemma 5 from [36], Lemma 12 from [36], Lemma 14/16 from [38], and Section 9) are prior published, parameter-free geometric lemmas whose stated assumptions do not include dynamic unit-disk range reporting; they are independent supports rather than a self-referential chain. No equation in the paper defines the claimed O(log n + k) query time into existence; epsilon, b, and r are asymptotic balancing constants. Hence the paper is not circular; the main weakness is the unproved transfer in Lemma 8, which belongs under correctness risk rather than circularity.

Assumptions & free parameters 3 free parameters · 7 assumptions · 0 invented entities

The paper's new results rest on several prior technical results, including two self-cited arc-specific infrastructures ([36], [38]); the most fragile is the transplant of the dynamic shallow-cutting framework (Lemma 8). No free parameters are fitted to data: the listed parameters are asymptotic balancing constants. Constants such as B, C, C' in Theorem 2 are fixed inside the proof to satisfy inequalities and do not affect the asymptotic form. No new physical or structural entities are postulated.

free parameters (3)
  • epsilon (asymptotic tuning)
    The bounds hold for any fixed epsilon > 0; used in log^{3+epsilon} n and log^{5+epsilon} n update times and in fan-out b = log^epsilon n. Not fitted to data; it is a degree of freedom in the asymptotic statement.
  • b (hierarchy fan-out) = log^epsilon n
    Set in Lemma 8 and Lemma 4 to balance update time and query time; b = log^epsilon n yields the quoted exponents.
  • r (deletion-only trade-off) = log n / log log n
    Set in Lemma 7 for the second deletion-only structure; controls O(r log n) deletion time vs O(log r + n/r) query time.
assumptions (7)
  • domain assumption Lemma 1 from [36]: a conforming coverage set of O(n) cells for P exists and can be computed in O(n log n) time.
    Static construction underpins the dynamic Lemma 2; taken as a black box from the authors' prior paper, not reproved here.
  • standard math Sharir's theorem [35]: the (<=k)-level of an arrangement of x-monotone curves that pairwise cross at most once has O(nk) vertices.
    Used in Lemma 9 to prove existence of shallow cuttings, following the template of Matousek [31].
  • standard math Random sampling and cutting existence results of Chazelle-Friedman [20] and Matousek [31] extend to pseudo-trapezoidal decompositions of the arc set Gamma.
    Lemma 9 is asserted by generalization; the details are not reproduced.
  • domain assumption Constant-size epsilon-cuttings with conflict lists exist for the arc set Gamma and can be computed in O(n) time (Lemma 12, from Chazelle [17] and Wang [36]).
    Used in Theorem 3 as the local cutting subroutine; cites the authors' own [36] for the arc version.
  • ad hoc to paper The dynamic shallow cutting hierarchy of Chan [10,11] and de Berg-Staals [7] carries over to x-monotone unit-circle arcs with the same amortized complexities (Lemma 8).
    The load-bearing transplant; the paper asserts it by analogy ('everything else is the same') without a full proof.
  • standard math Wang-Zhao [38] Lemma 9 and the alpha-hull duality of Edelsbrunner et al. [26]: lower envelope layers of Gamma correspond to lower alpha-hull layers of the point set.
    Basis of the static algorithm in Section 8; prior published results for arcs are used as facts.
  • standard math Every two arcs of Gamma cross at most once (equal-radius circles), so the arrangement has the standard Davenport-Schinzel-type structure.
    Invoked throughout (e.g., Observation 2, Lemma 9, Lemma 14); it is a known property of unit circles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dynamic Unit-Disk Range Reporting." pith.science (2026). https://pith.science/paper/U7OGCNLV

@misc{pith2026250100120,
  author       = {Pith},
  title        = {Pith review of: Dynamic Unit-Disk Range Reporting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U7OGCNLV}},
  note         = {Machine review of arXiv:2501.00120}
}
abstract

For a set $P$ of $n$ points in the plane and a value $r > 0$, the unit-disk range reporting problem is to construct a data structure so that given any query disk of radius $r$, all points of $P$ in the disk can be reported efficiently. We consider the dynamic version of the problem where point insertions and deletions of $P$ are allowed. The previous best method provides a data structure of $O(n\log n)$ space that supports $O(\log^{3+\epsilon}n)$ amortized insertion time, $O(\log^{5+\epsilon}n)$ amortized deletion time, and $O(\log^2 n/\log\log n+k)$ query time, where $\epsilon$ is an arbitrarily small positive constant and $k$ is the output size. In this paper, we improve the query time to $O(\log n+k)$ while keeping other complexities the same as before. A key ingredient of our approach is a shallow cutting algorithm for circular arcs, which may be interesting in its own right. A related problem that can also be solved by our techniques is the dynamic unit-disk range emptiness queries: Given a query unit disk, we wish to determine whether the disk contains a point of $P$. The best previous work can maintain $P$ in a data structure of $O(n)$ space that supports $O(\log^2 n)$ amortized insertion time, $O(\log^4n)$ amortized deletion time, and $O(\log^2 n)$ query time. Our new data structure also uses $O(n)$ space but can support each update in $O(\log^{1+\epsilon} n)$ amortized time and support each query in $O(\log n)$ time.

Figures

Figures reproduced from arXiv: 2501.00120 by the authors.

Figure 1
Figure 1. The point-zones lie in the grey area. The black dots are points of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Illustrating the case where C ∗ is a regular cell. The red box is ⊞C∗ . The two blue vertical lines are vertical point-zone bounding lines; the left one is ℓ ∗ . All grey cells are in vertical point-zones while cells are in vertical gap zones. Case (1): The interior of ⊞C∗ does not intersect any point-zone bounding line. In this case, ⊞C∗ must be inside a vertical point-zone and also inside a horizontal point-zone. … view at source ↗
Figure 3
Figure 3. Illustrating the new grid after the update on Figure [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (18 more)
Figure 4
Figure 4. Figure 4: Illustrating the case where C ∗ is in a vertical gap-zone. The red box is ⊞C∗ . All grey cells are in vertical point-zones while white cells are in vertical gap zones. ℓ1 and ℓ2 are respectively the left and right bounding lines of the vertical gap-zone containing C ∗ …
Figure 5
Figure 5. Figure 5: Illustration the boundary of Hℓ(Q), where Q is the set of points below the x-axis ℓ. It consists of three (blue) dashed horizontal line segments of y-coordinates −1, four (red) dotted R +- constrained arcs with centers on ℓ, and four other solid R +-constrained arcs. T…
Figure 6
Figure 6. Figure 6: Illustration the wings of the a point q. The two (red) dotted curves are wing arcs and the two (blue) dashed segments are wing half-lines. p and p ′ are the left and right wing vertices, respectively. ` x q q 0 p p 0 [PITH_FULL_IMAGE:figures/full_fig_p020_6.png]
Figure 7
Figure 7. Figure 7: Illustration two points q and q ′ that are in far-away position. The two (red) dotted arcs and the (blue) dashed segments in between constitute β(q, q′ ). Far-away position. Consider two points q, q′ ∈ R − such that x(q) < x(q ′ ). We say that (q, q′ ) are in far-away …
Figure 8
Figure 8. Figure 8: Illustrating the proof of Γ∆′ = ∅, with ∆′ = R ∪ ∆, where R is the gray rectangle and ∆ is the region below e. Lemma 11 A (k, K)-shallow cutting of size t in the vertex-segment form can be transformed into a (k, 3K)-shallow cutting of size O(t) in the bottom-open pseud…
Figure 9
Figure 9. Figure 9: Illustrating the notation for processing [PITH_FULL_IMAGE:figures/full_fig_p026_9.png]
Figure 10
Figure 10. Figure 10: Illustrating the notation for processing [PITH_FULL_IMAGE:figures/full_fig_p027_10.png]
Figure 11
Figure 11. Figure 11: Illustrating the lower envelope U1. Black dotted arcs are boundaries of unit disks centered at points of Q. The point q1 is below U1 while q2 is above U1. ` U1 [PITH_FULL_IMAGE:figures/full_fig_p029_11.png]
Figure 13
Figure 13. Figure 13: The three blue arcs are below q while the two red arcs are above q. ` U1 q γj−1 γj γj+1 γj+2 u aj aj+1 [PITH_FULL_IMAGE:figures/full_fig_p030_13.png]
Figure 15
Figure 15. Figure 15: Illustrating layers of lower envelopes U1, U2, U3. the portion of γj+1 between aj+1 and u. As x(q) < x(u), this implies that q cannot be above γj+1 and thus pj+1 cannot be in Dq. • If γ ′ j and γ ′ j+1 do not intersect, then both the right endpoint bj of γj and the le…
Figure 16
Figure 16. Figure 16: Illustrating the α-hull of Q, for α = −1. h1 H1 U1 h2 h3 h4 u1 u2 u3 [PITH_FULL_IMAGE:figures/full_fig_p032_16.png]
Figure 18
Figure 18. Figure 18: Illustrating lower α-hull layers {H1, H2, H3}. Our goal is to compute the lower envelope layers {Ui}. Instead of computing them directly, we consider a dual problem. We borrow a concept α-hull from [26], which is a generalization of the convex hull. For a real number …
Figure 19
Figure 19. Figure 19: Illustrating the graph G for a set Q = {p1, p2, ..., p8} of 8 points. p1 p2 p8 γ(p1, p3) γ(p6, p7) γ(p3, p6) [PITH_FULL_IMAGE:figures/full_fig_p033_19.png]
Figure 21
Figure 21. Figure 21: Illustrating the adjacency lists Ll(p) and Lr(p) at p. The two red arcs are bottom edges. The red dashed segment with arrow is the tangent ray of γ(p, q) at p and the tangent angle is shown. 8.2 Constructing the tree graph G The following lemma will be used as a subro…
Figure 22
Figure 22. Figure 22: p is an endpoint of γ(vi), i.e., the common tangent arc (the red arc) of the new H(vi−1) and H(v). way, G(v) can be computed in O(|Q(u)| + |Q(w)|) time, or in O(|Q(v)|) time as Q(v) = Q(u) ∪ Q(w). Hence, the total time for constructing the graph G is O(n log n) and th…
Figure 23
Figure 23. Figure 23: Illustrating points a ′ , b ′ and c ′ , angles {β1, β2, β3} and {ϵ1, ϵ2}. x y1 y2 6 (xy1, xy2) [PITH_FULL_IMAGE:figures/full_fig_p036_23.png]
Figure 25
Figure 25. Figure 25: Illustrating the case of pulling up p in which ϵ1 becomes null. p a b c H(vi−1) L(v) a 0 b 0 c 0 [PITH_FULL_IMAGE:figures/full_fig_p036_25.png]
Figure 27
Figure 27. Figure 27: Illustrating the definitions of a ∗ , b ∗ , and c ∗ . now is “promoted” to be a vertex of H(vi)). Since the height of T is O(log n), the total number of promotions for deleting all points p ∈ G is bounded by O(n log n). On the other hand, if a vertex u is wrapped by b…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 20 canonical work pages

  1. [36]

    Unit-disk range searching and applications

    Haitao Wang. Unit-disk range searching and applications. Journal of Computational Geometry , 14:343–394, 2023. doi:10.20382/jocg.v14i1a13. 3, 4, 15, 18, 24

    doi:10.20382/jocg.v14i1a13 2023

  2. [38]

    Computing the minimum bottleneck moving spanning tree

    Haitao Wang and Yiming Zhao. Computing the minimum bottleneck moving spanning tree. In Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 82:1–82:15, 2022. doi:10.4230/LIPIcs.MFCS.2022.82. 3, 29, 30, 33, 38

    work page doi:10.4230/lipics.mfcs.2022.82 2022

  3. [12]

    Timothy M. Chan. Dynamic geometric data structures via shallow cuttings. Discrete and Com- putational Geometry , 64:1235–1252, 2020. doi:10.1007/s00454-020-00229-5 . 2, 13, 16, 18, 38

    work page doi:10.1007/s00454-020-00229-5 2020

  4. [1]

    Peyman Afshani and Timothy M. Chan. Optimal halfspace range reporting in three dimensions. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 180–186, 2009. doi:10.1137/1.9781611973068.21. 1, 2

    work page doi:10.1137/1.9781611973068.21 2009

  5. [2]

    Pankaj K. Agarwal. Range searching, in Handbook of Discrete and Computational Geometry, C.D. T´ oth, J. O’Rourke, and J.E. Goodman (eds.), pages 1057–1092. CRC Press, 3rd edition,

  6. [3]

    Pankaj K. Agarwal. Simplex range searching and its variants: a review. In A Journey Through Discrete Mathematics, pages 1–30. Springer, 2017. doi:10.1007/978-3-319-44479-6_1 . 1

    doi:10.1007/978-3-319-44479-6_1 2017

  7. [4]

    Agarwal and Micha Sharir

    Pankaj K. Agarwal and Micha Sharir. Pseudoline arrangements: Duality, algorithms, and ap- plications. SIAM Journal on Computing , 34:526–552, 2005. doi:10.1137/S0097539703433900. 18

    doi:10.1137/s0097539703433900 2005

  8. [5]

    Bentley and Hermann A

    Jon L. Bentley and Hermann A. Maurer. A note on Euclidean near neighbor searching in the plane. Information Processing Letters, 8:133–136, 1979. 1

    work page 1979

Show all 41 references
  1. [6]

    van Kreveld, and Mark H

    Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational Geometry — Algorithms and Applications . Springer-Verlag, Berlin, 3rd edition, 2008. 1, 17

    2008

  2. [7]

    Dynamic data structures for k-nearest neighbor queries

    Sarita de Berg and Frank Staals. Dynamic data structures for k-nearest neighbor queries. Compu- tational Geometry: Theory and Applications , 111(101976), 2023. doi:10.1016/j.comgeo.2022. 101976. 2, 13, 14, 15, 17, 18

    2023 doi

  3. [8]

    Timothy M. Chan. Random sampling, halfspace range reporting, and construction of ( ≤ k)- levels in three dimensions. SIAM Journal on Computing , 20:561–575, 2000. doi:10.1137/ S0097539798349188. 2, 13

  4. [9]

    Timothy M. Chan. Dynamic planar convex hull operations in near-logarithmaic amortized time. Journal of the ACM , 48:1–12, 2001. doi:10.1145/363647.363652. 38

    2001

  5. [10]

    Timothy M. Chan. A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. Journal of the ACM , 57:16:1–16:15, 2010. doi:10.1145/1706591.1706596. 2, 13, 16

    2010

  6. [11]

    Timothy M. Chan. Three problems about dynamic convex hulls. International Journal of Com- putational Geometry and Applications , 22:341–364, 2012. doi:10.1142/S0218195912600096. 2, 13, 14, 15, 16, 17

    2012 doi

  7. [13]

    Chan and Dimitrios Skrepetos

    Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. In Proceedings of the 27th International Symposium on Algorithms and Com- putation (ISAAC), pages 24:1–24:13, 2016. doi:10.4230/LIPIcs.ISAAC.2016.24. 3

    2016 doi

  8. [14]

    Chan and Konstantinos Tsakalidis

    Timothy M. Chan and Konstantinos Tsakalidis. Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. Discrete and Computational Geometry , 56:866–881, 2016. doi:10.1007/ s00454-016-9784-4 . 1, 2, 13, 15, 16, 18, 24

    2016

  9. [15]

    An improved algorithm for the fixed-radius neighbor problem

    Bernard Chazelle. An improved algorithm for the fixed-radius neighbor problem. Information Processing Letters, 16:193–198, 1983. doi:10.1016/0020-0190(83)90123-0. 1 39

    1983 doi

  10. [16]

    On the convex layers of a planar set

    Bernard Chazelle. On the convex layers of a planar set. IEEE Transactions on Information Theory, 31(4):509–517, 1985. doi:10.1109/TIT.1985.1057060. 32

    1985

  11. [17]

    Cutting hyperplanes for divide-and-conquer

    Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete and Computational Geometry, 9(2):145–158, 1993. doi:10.1007/BF02189314. 24

    1993 doi

  12. [18]

    Preparata, and Chee-Keng Yap

    Bernard Chazelle, Richard Cole, Franco P. Preparata, and Chee-Keng Yap. New upper bounds for neighbor searching. Information and Control , 68:105–124, 1986. doi:10.1016/S0019-9958(86) 80030-4. 1

    1986 doi

  13. [19]

    Optimal solutions for a class of point retrieval prob- lems

    Bernard Chazelle and Herbert Edelsbrunner. Optimal solutions for a class of point retrieval prob- lems. Journal of Symbolic Computation , 1:47–56, 1985. doi:10.1016/S0747-7171(85)80028-6. 1

    1985 doi

  14. [20]

    A deterministic view of random sampling and its use in geometry

    Bernard Chazelle and Joel Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10:229–249, 1990. doi:10.1007/BF02122778. 18

    1990 doi

  15. [21]

    Bernard Chazelle and Leonidas J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133–162, 1986. doi:10.1007/BF01840440. 2, 31

    1986 doi

  16. [22]

    Bernard Chazelle and Leonidas J. Guibas. Fractional cascading: II. Applications. Algorithmica, 1:163–191, 1986. doi:10.1007/BF01840441. 2, 31

    1986 doi

  17. [23]

    Guibas, and D.T

    Bernard Chazelle, Leonidas J. Guibas, and D.T. Lee. The power of geometric duality. BIT, 25:76–90, 1985. doi:10.1007/BF01934990. 2

    1985 doi

  18. [24]

    Adrian Dumitrescu, Anirban Ghosh, and Csaba D. T´ oth. Sparse hop spanners for unit disk graphs. Computational Geometry: Theory and Applications , 100:101808: 1–14, 2022. doi:10. 1016/j.comgeo.2021.101808. 32

    2022

  19. [25]

    Guibas, and J

    Herbert Edelsbrunner, Leonidas J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing , 15(2):317–340, 1986. doi:10.1137/0215023. 37

    1986 doi

  20. [26]

    Kirkpatrick, and Raimund Seidel

    Herbert Edelsbrunner, David G. Kirkpatrick, and Raimund Seidel. On the shape of a set of points in the plane. IEEE Transactions on Information Theory , 29:551–559, 1983. doi:10.1109/TIT. 1983.1056714. 18, 19, 32

    1983

  21. [27]

    Frederickson

    G.N. Frederickson. An optimal algorithm for selection in a min-heap. Information and Compu- tation, 104:197–214, 1993. doi:10.1006/inco.1993.1030. 17

    1993

  22. [28]

    Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications

    Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. Discrete and Computational Geometry, 64:838–904, 2020. doi:10.1007/s00454-020-00243-7 . 2, 13, 16

    2020 doi

  23. [29]

    Kirkpatrick

    David G. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing , 12(1):28–35, 1983. doi:10.1137/0212002. 37

    1983 doi

  24. [30]

    Efficient partition trees.Discrete and Computational Geometry , 8(3):315–334,

    Ji˘ r ´ ı Matouˇ sek. Efficient partition trees.Discrete and Computational Geometry , 8(3):315–334,

  25. [31]

    Reporting points in halfspaces.Computational Geometry: Theory and Applica- tions, 2:169–186, 1992

    Jiˇ r ´ ı Matouˇ sek. Reporting points in halfspaces.Computational Geometry: Theory and Applica- tions, 2:169–186, 1992. doi:10.1016/0925-7721(92)90006-E. 18

    1992 doi

  26. [32]

    Geometric range searching.ACM Computing Survey , 26:421–461, 1994

    Jiˇ r ´ ı Matouˇ sek. Geometric range searching.ACM Computing Survey , 26:421–461, 1994. doi: 10.1145/197405.197408. 1 40

    1994

  27. [33]

    Edgar A. Ramos. On range reporting, ray shooting and k-level construction. In Proceedings of the 15th Annual Symposium on Computational Geometry (SoCG) , pages 390–399, 1999. doi: 10.1145/304893.304993. 1

    1999

  28. [34]

    Neil Sarnak and Robert E. Tarjan. Planar point location using persistent search trees. Commu- nications of the ACM , 29:669–679, 1986. doi:10.1145/6138.6151. 37

    1986

  29. [35]

    On k-sets in arrangements of curves and surfaces

    Micha Sharir. On k-sets in arrangements of curves and surfaces. Discrete and Computational Geometry, 6:593–613, 1991. doi:10.1007/BF02574706. 18

    1991 doi

  30. [37]

    Near-optimal algorithms for shortest paths in weighted unit- disk graphs

    Haitao Wang and Jie Xue. Near-optimal algorithms for shortest paths in weighted unit- disk graphs. Discrete and Computational Geometry , 64:1141–1166, 2020. doi:10.1007/ s00454-020-00219-7 . 3

    2020

  31. [39]

    An optimal algorithm for L1 shortest paths in unit-disk graphs

    Haitao Wang and Yiming Zhao. An optimal algorithm for L1 shortest paths in unit-disk graphs. Computational Geometry: Theory and Applications , 110:101960: 1–9, 2023. doi:10.1016/j. comgeo.2022.101960. 3

    2023

  32. [40]

    Reverse shortest path problem for unit-disk graphs

    Haitao Wang and Yiming Zhao. Reverse shortest path problem for unit-disk graphs. Journal of Computational Geometry, 14:14–47, 2023. doi:10.20382/jocg.v14i1a2. 3 41

    2023 doi

  33. [1992]

    doi:10.1007/BF02293051. 14, 15

    doi

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.