Selection and sorting in totally monotone arrays

DOI10.1007/BF02090398zbMATH Open0766.68022OpenAlexW3138958529MaRDI QIDQ3979609FDOQ3979609

Authors Dina Kravets, James K. Park

Publication date 26 June 1992

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02090398

zbMATH Keywords

totally monotone array

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• IMPROVED SELECTION IN TOTALLY MONOTONE ARRAYS
• Superlinear bounds for matrix searching problems
• Geometric applications of a matrix-searching algorithm
• Selection in Monotone Matrices and Computingkth Nearest Neighbors
• scientific article; zbMATH DE number 742987

Cites work

• scientific article; zbMATH DE number 432797 (Why is no real title available?)
• scientific article; zbMATH DE number 18528 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A linear time algorithm for finding all farthest neighbors in a convex polygon
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• A linear-time algorithm for concave one-dimensional dynamic programming
• A note on the all nearest-neighbor problem for convex polygons
• Edge-skeletons in arrangements with applications
• Efficient Parallel Algorithms for String Editing and Related Problems
• Geometric applications of a matrix-searching algorithm
• How good is the information theory bound in sorting?
• On the convex layers of a planar set
• Sequence comparison with mixed convex and concave costs
• Some techniques for geometric searching with implicit set representations
• The all nearest-neighbor problem for convex polygons
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• The concave least-weight subsequence problem revisited
• Time bounds for selection

Cited in

(7)

• Applications of generalized matrix searching to geometric algorithms
• Geometric applications of a matrix-searching algorithm
• scientific article; zbMATH DE number 742987 (Why is no real title available?)
• Perspectives of Monge properties in optimization
• Selection in monotone matrices and computing k th nearest neighbors
• IMPROVED SELECTION IN TOTALLY MONOTONE ARRAYS
• Searching monotone multi-dimensional arrays

This page was built for publication: Selection and sorting in totally monotone arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3979609)