Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12146
- Type
- D - Journal article
- DOI
-
10.1007/s00454-016-9784-4
- Title of journal
- Discrete and Computational Geometry: an international journal of mathematics and computer science
- Article number
- 4
- First page
- 866
- Volume
- 56
- Issue
- 4
- ISSN
- 0179-5376
- Open access status
- Technical exception
- Month of publication
- May
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 10
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- A preliminary version of this paper appeared at SoCG'15 and was invited to the journal special issue for highlights from the conference. It is discussed in four chapters of the "Handbook on Discrete & Computational Geometry" (28 "Arrangements", 32 "Proximity Algorithms", 40 "Range Searching", and 44 "Randomization and derandomization") and two chapters of "A Journey Through Discrete Mathematics" ("Simplex Range Searching and Its Variants" and "Approximating the k-Level in Three-Dimensional Plane Arrangements"). The results have been used, for example, in "Affine invariants of generalized polygons and matching under affine transformations." (Comp.Geom.'16) and "Spanners for Directed Transmission Graphs" (SICOMP'18).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -