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

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

52A10: Convex sets in (2) dimensions (including convex curves)

15A99: Basic linear algebra

Related Items

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

Cites Work