Geometric applications of a matrix-searching algorithm

DOI10.1007/BF01840359zbMath0642.68078WikidataQ29027819 ScholiaQ29027819MaRDI QIDQ1101223

Robert Wilber, Maria M. Klawe, Alok Aggarwal, Shlomo Moran, Peter W. Shor

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

convex polygon geometric algorithms computational geometry monotone matrix inscribed polygons wire routing all-farthest-neighbors circumscribed polygons

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Convex sets in (2) dimensions (including convex curves) (52A10) Basic linear algebra (15A99)

Related Items

Absent Subsequences in Words, Linear-space S-table algorithms for the longest common subsequence problem, A Dynamic Programming Approach to Power Consumption Minimization in Gunbarrel Natural Gas Networks with Nonidentical Compressor Units, Unnamed Item, Unnamed Item, Unnamed Item, Fast parallel algorithms for the maximum empty rectangle problem., Scheduling with batching: Two job types, Unnamed Item, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Efficient Algorithm for Computing the Triangle Maximizing the Length of Its Smallest Side Inside a Convex Polygon, Unnamed Item, The convex-hull-and-line traveling salesman problem: A solvable case, Finding least-weight subsequences with fewer processors, Finding a largest-area triangle in a terrain in near-linear time, Finding a minimum-weight $k$-link path in graphs with the concave Monge property and applications, Subcontracting and lot-sizing with constant capacities, On the symmetric angle-restricted nearest neighbor problem, An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays, Strongly polynomial efficient approximation scheme for segmentation, Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search, Online dynamic programming speedups, Approximating points by a piecewise linear function, Selection and sorting in totally monotone arrays, Selection in monotone matrices and computing k th nearest neighbors, An Algorithm to Compute Any Simple $k$-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest, Approximate regular expression pattern matching with concave gap penalties, Dynamic programming algorithms for the mosaic longest common subsequence problem, Efficient algorithms for finding interleaving relationship between sequences, A unified linear-time algorithm for computing distance maps, An optimal algorithm for finding the separation of simple polygons, Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance, $k$ best cuts for circular-arc graphs, Finding a closet visible vertex pair between two polygons, Dynamic lot-sizing model for major and minor demands, On the recognition of permuted bottleneck Monge matrices, Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon, Parallel computational geometry, Speeding up the AIFV-2 dynamic programs by two orders of magnitude using range minimum queries, A note on lower bounds for the maximum area and maximum perimeter k-gon problems, Maximizing the overall end-user satisfaction of data broadcast in wireless mesh networks, Spanning trees and shortest paths in Monge graphs, Structured $p$-facility location problems on the line solvable in polynomial time, Perspectives of Monge properties in optimization, One-dimensional approximate point set pattern matching with $L_p$-norm, Improved algorithms for path partition and related problems, Unified compression-based acceleration of edit-distance computation, Monge properties of sequence alignment, Sequence Alignment Algorithms for Run-Length-Encoded Strings, On finding an empty staircase polygon of largest area (width) in a planar point-set, Unnamed Item, Monge properties, discrete convexity and applications, An almost linear time algorithm for field splitting in radiation therapy, Estimation of Monge matrices, Unnamed Item, A linear-time algorithm for concave one-dimensional dynamic programming, On the angle restricted nearest neighbor problem, Minimizing the continuous diameter when augmenting a geometric tree with a shortcut, Computing Euclidean maximum spanning trees, Empty squares in arbitrary orientation among points, Applications of generalized matrix searching to geometric algorithms, An optimal algorithm with unknown time complexity for convex matrix searching, Computing the longest diagonal of a simple polygon, Largest triangles in a polygon, A special case of the $n$-vertex traveling-salesman problem that can be solved in O($n$) time, Finding minimum area $k$-gons, Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks, Discovering recurring activity in temporal networks, Largest and smallest area triangles on imprecise points, Dynamic programming with convexity, concavity and sparsity, Finding the largest area axis-parallel rectangle in a polygon, On the number of maximum empty boxes amidst $n$ points, Efficient algorithms for the largest rectangle problem, A dynamic data structure for top-$k$ queries on uncertain data, New algorithms for facility location problems on the real line, Optimal time bounds for some proximity problems in the plane, Monge and feasibility sequences in general flow problems, Geometric Knapsack problems, On almost Monge all scores matrices, A generalization of magic squares with applications to digital halftoning, Finding maximum edge bicliques in convex bipartite graphs, Shape rectangularization problems in intensity-modulated radiation therapy, The algebraic Monge property and path problems, Coupled path planning, region optimization, and applications in intensity-modulated radiation therapy, An improved algorithm for tree edit distance with applications for RNA secondary structure comparison, Minimizing a sum of submodular functions, $L_{1}$ shortest path queries in simple polygons, Unnamed Item, EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION, Speeding up dynamic programming in the line-constrained $k$-median, Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood, A Monge property for the $d$-dimensional transportation problem, On the modality of convex polygons, Deterministic Algorithms for Unique Sink Orientations of Grids, GEOMETRIC ALGORITHMS FOR THE CONSTRAINED 1-D K-MEANS CLUSTERING PROBLEMS AND IMRT APPLICATIONS, Speeding up Dynamic Programming in the Line-Constrained k-median, Scheduling with gaps: new models and algorithms, Extremal convex polygons inscribed in a given convex polygon, Properties of the $d$-dimensional Earth mover's problem, Sparse LCS common substring alignment, Alignments with non-overlapping moves, inversions and tandem duplications in $O(n^{4})$ time, Optimal shortest path queries in a simple polygon, The complexity of optimization on grids, Hausdorff approximation of convex polygons, Monge strikes again: Optimal placement of web proxies in the internet, Optimum extensions of prefix codes., Computing the $L_1$ geodesic diameter and center of a simple polygon in linear time, A faster off-line algorithm for the TCP acknowledgement problem., Fast distance multiplication of unit-Monge matrices, On optimal bridges between two convex regions, Resequencing a set of strings based on a target string, Fast and longest rollercoasters

Cites Work