Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons
From MaRDI portal
Publication:834601
DOI10.1007/s00453-008-9221-zzbMath1191.68835OpenAlexW1997489418MaRDI QIDQ834601
Jakub Pawlewicz, Mihai Pǎtraşcu
Publication date: 27 August 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9221-z
Nonnumerical algorithms (68W05) Number-theoretic algorithms; complexity (11Y16) Farey sequences; the sequences (1^k, 2^k, dots) (11B57)
Related Items (3)
From prima quadraginta octant to lattice sphere through primitive integer operations ⋮ On the Farey sequence and its augmentation for applications to image analysis ⋮ Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Scaled density models for binary response data and their \(D\)- and \(D_s\)-optimal designs
- On the number of primitive lattice points in plane domains
- Optimal search for rationals
- Primitive lattice points in rational ellipses and related arithmetic functions
- Rational search
- Efficient search for rationals
- Primitive lattice points in starlike planar sets
- Distribution of lattice points visible from the origin
- On the primitive circle problem
- Explicit and efficient formulas for the lattice point count in rational polygons using Dedekind-Rademacher sums
- The number of lattice points within a contour and visible from the origin
- Primitive lattice points in a thin strip along the boundary of a large convex planar domain
- Primitive lattice points inside an ellipse
- Order Statistics in the Farey Sequences in Sublinear Time
- Computing the Summation of the Möbius Function
- On primitive lattice points in planar domains
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- On the number of coprime integer pairs within a circle
- On sums and differences of two relative prime cubes
- Primitive lattice points in convex planar domains
- Approximating Rational Numbers by Fractions
This page was built for publication: Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons