Maintenance of configurations in the plane

DOI10.1016/0022-0000(81)90012-XzbMath0474.68082OpenAlexW2132445073MaRDI QIDQ1158972

Publication date: 1981

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(81)90012-x

zbMATH Keywords

computational geometry convex hulls maximal elements halfspaces dynamization

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Related Items

Tight degree bounds for pseudo-triangulations of points, An optimal algorithm for plane matchings in multipartite geometric graphs, A note on finding a maximum empty rectangle, Ray shooting in polygons using geodesic triangulations, The power of geometric duality, I/O-efficient 2-d orthogonal range skyline and attrition priority queues, Dynamic layers of maxima with applications to dominating queries, Exact algorithms for size constrained 2-clustering in the plane, Compressing spatio-temporal trajectories, Tangential cover for thick digital curves, Dynamic coresets, On-line updating of solutions to a class of matroid intersection problems, An Optimal Algorithm for Plane Matchings in Multipartite Geometric Graphs, Dynamic half-space range reporting and its applications, Approximating points by a piecewise linear function, Dynamic Euclidean minimum spanning trees and extrema of binary functions, Computing the Fréchet distance with a retractable leash, On determining the on-line minimax linear fit to a discrete point set in the plane, An introduction to randomization in computational geometry, In-place algorithms for computing (Layers of) maxima, Geometric applications of a matrix-searching algorithm, Parallel algorithms for some functions of two convex polygons, Kinetic and dynamic data structures for convex hulls and upper envelopes, COMPUTING CLOSEST POINTS FOR SEGMENTS, An O(log n) time parallel algorithm for triangulating a set of points in the plane, On geometric optimization with few violated constraints, Finding the convex hull of a sorted point set in parallel, On O(\(\sqrt{n})\) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors, Parallel computational geometry, An efficient algorithm for maxdominance, with applications, Connecting colored point sets, Finding a minimum independent dominating set in a permutation graph, Space-efficient planar convex hull algorithms, An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem, Efficient splitting and merging algorithms for order decomposable problems, A discrete geometry approach for dominant point detection, The density maximization problem in graphs, Indexing moving points, Covering moving points with anchored disks, Two general methods for dynamizing decomposable searching problems, Separating bichromatic point sets by L-shapes, General methods for 'all elements' and 'all pairs' problems, A kinetic triangulation scheme for moving points in the plane, Minimizing the error of linear separators on linearly inseparable data, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, Minimizing the diameter of a spanning tree for imprecise points, A faster algorithm for the maximum weighted tardiness problem, Recursion and parallel algorithms in geometric modeling problems, Dynamic geometric data structures via shallow cuttings, Computational geometry algorithms for the systolic screen, Relative convex hulls in semi-dynamic arrangements, A new data structure for shortest path queries in a simple polygon, On the dynamic maintenance of maximal points in the plane, Output-sensitive peeling of convex and maximal layers, Off-line dynamic maintenance of the width of a planar point set, Perfect binary space partitions, Dynamic Planar Range Maxima Queries, Optimal simplification of polygonal chains for subpixel-accurate rendering, Applications of a semi-dynamic convex hull algorithm, Special subgraphs of weighted visibility graphs, Parallel methods for visibility and shortest-path problems in simple polygons, AN EXPERIMENTAL STUDY OF ON-LINE METHODS FOR ZONE CONSTRUCTION IN ARRANGEMENTS OF LINES IN THE PLANE, Covering a simple polygon by monotone directions, Enumerating pseudo-triangulations in the plane, Convex hull properties and algorithms, ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS, k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON, Algorithms for Problems on Maximum Density Segment, Covering Points with Convex Sets of Minimum Size, A fast algorithm for the alpha-connected two-center decision problem, An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains, A fast algorithm for computing sparse visibility graphs, Implicitly representing arrangements of lines or segments, On some geometric selection and optimization problems via sorted matrices, A new approach to the dynamic maintenance of maximal points in a plane, Output-sensitive results on convex hulls, extreme points, and related problems, Computing shortest transversals, The projection median of a set of points, Fast detection of polyhedral intersection, Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time, Optimal shortest path queries in a simple polygon, Median hyperplanes in normed spaces -- a survey, Two approaches to building time-windowed geometric data structures, Applications of mathematics to maritime search, Cutting bamboo down to size, Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane, Efficient searching with linear constraints, An efficient algorithm for the parametric resource allocation problem, Efficient splitting and merging algorithms for order decomposable problems., Maintaining AUC and \(H\)-measure over time, On the definition and computation of rectilinear convex hulls, On the planar two-center problem and circular hulls, A matching problem in the plane, On embedding an outer-planar graph in a point set, Parallel solutions to geometric problems in the scan model of computation, Determining Weak Visibility of a Polygon from an Edge in Parallel, COMPUTING CONSTRAINED SHORTEST SEGMENTS: BUTTERFLY WINGSPANS IN LOGARITHMIC TIME, OPTIMAL LINE BIPARTITIONS OF POINT SETS, Center problems with pos/neg weights on trees, The maximum-level vertex in an arrangement of lines, Constrained square-center problems, The two-line center problem from a polar view: a new algorithm and data structure, Computing common tangents without a separating line, Divide and Conquer Method for k-Set Polygons, ON THE LOCAL PROPERTIES OF DIGITAL CURVES, A simplified technique for hidden-line elimination in terrains, Cartographic line simplication and polygon CSG formulae in O(n log* n) time, The centroid of points with approximate weights, Dynamic convex hulls under window-sliding updates, Dynamic connectivity in disk graphs, MAINTAINING VISIBILITY INFORMATION OF PLANAR POINT SETS WITH A MOVING VIEWPOINT, Compressing Spatio-temporal Trajectories, A consistent semantics of self-adjusting computation, Dynamic Algorithms for Visibility Polygons in Simple Polygons, Applications of a semi-dynamic convex hull algorithm, Unnamed Item, Unnamed Item, Unnamed Item, On some geometric selection and optimization problems via sorted matrices, Weighted Rectilinear Approximation of Points in the Plane, Tangential Cover for Thick Digital Curves, Minimizing Distance-to-Sight in Polygonal Domains, On Top-k Weighted<scp>Sum</scp>Aggregate Nearest and Farthest Neighbors in the L1 Plane, Dynamic data structures for fat objects and their applications, Plane 3-Trees: Embeddability and Approximation

Cites Work