Applications of a semi-dynamic convex hull algorithm
From MaRDI portal
Publication:1196456
DOI10.1007/BF01994880zbMath0761.68097OpenAlexW2042473201MaRDI QIDQ1196456
Subhash Suri, J. E. Hershberger
Publication date: 14 December 1992
Published in: BIT (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01994880
Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Deterministic scheduling theory in operations research (90B35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Tight degree bounds for pseudo-triangulations of points, Minimization and maximization versions of the quadratic travelling salesman problem, An optimal algorithm for plane matchings in multipartite geometric graphs, New variants of perfect non-crossing matchings, Packing plane spanning trees and paths in complete geometric graphs, An Optimal Algorithm for Plane Matchings in Multipartite Geometric Graphs, Dynamic half-space range reporting and its applications, PARTITIONING COLORED POINT SETS INTO MONOCHROMATIC PARTS, Boundary labeling: Models and efficient algorithms for rectangular maps, On inducing polygons and related problems, Weighted \(L_{\infty}\) isotonic regression, Fitting a two-joint orthogonal chain to a point set, Complexity results on untangling red-blue matchings, The centroid of points with approximate weights, Dynamic convex hulls under window-sliding updates, On Hamiltonian alternating cycles and paths, On bounded leg shortest paths problems, Augmenting the edge connectivity of planar straight line graphs to three, Connectivity guarantees for wireless networks with directional antennas, Covering point sets with two disjoint disks or squares, Relative convex hulls in semi-dynamic arrangements, Spiral Serpentine Polygonization of a Planar Point Set, New variants of perfect non-crossing matchings, INDUCING POLYGONS OF LINE ARRANGEMENTS, Algorithms for optimal outlier removal, On Map Labeling with Leaders, Two approaches to building time-windowed geometric data structures, Convex hull of a planar set of straight and circular line segments, Bipartite embeddings of trees in the plane, Geometric biplane graphs. II: Graph augmentation, Isotonic regression for multiple independent variables, On embedding an outer-planar graph in a point set
Cites Work
- Unnamed Item
- Unnamed Item
- Problem-solving through problems
- A faster algorithm for the maximum weighted tardiness problem
- A matching problem in the plane
- An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem
- Maintenance of configurations in the plane
- An efficient algorithm for determining the convex hull of a finite planar set
- COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
- Finding tailored partitions
- On the convex layers of a planar set
- The Ultimate Planar Convex Hull Algorithm?
- An optimal real-time algorithm for planar convex hulls
- Optimal Sequencing of a Single Machine Subject to Precedence Constraints
