Selection and sorting in totally monotone arrays

DOI10.1007/BF02090398zbMath0766.68022OpenAlexW3138958529MaRDI QIDQ3979609

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)

Related Items

Selection in monotone matrices and computing k th nearest neighbors ⋮ Perspectives of Monge properties in optimization

Cites Work

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