Maintenance of configurations in the plane
From MaRDI portal
Publication:1158972
DOI10.1016/0022-0000(81)90012-XzbMATH Open0474.68082OpenAlexW2132445073MaRDI QIDQ1158972FDOQ1158972
Authors: Mark H. Overmars, J. Van Leeuwen 
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
Discrete mathematics in relation to computer science (68R99) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms in computer science (68W99)
Cites Work
- Title not available (Why is that?)
- An efficient algorithm for determining the convex hull of a finite planar set
- Title not available (Why is that?)
- On Finding the Maxima of a Set of Vectors
- Title not available (Why is that?)
- Decomposable searching problems
- Time bounds for selection
- Title not available (Why is that?)
- The 1972 Wald Lecture Robust Statistics: A Review
- Title not available (Why is that?)
- On the identification of the convex hull of a finite set of points in the plane
- Convex hulls of finite sets of points in two and three dimensions
- An Optimal Algorithm for Finding the Kernel of a Polygon
- Title not available (Why is that?)
- An optimal real-time algorithm for planar convex hulls
- Title not available (Why is that?)
- Divide and conquer for linear expected time
- A Lower Bound to Finding Convex Hulls
- Constructing the convex hull of a set of points in the plane
- On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
- Uniform convergence of the empirical distribution function over convex sets
Cited In (only showing first 100 items - show all)
- An efficient algorithm for the parametric resource allocation problem
- On the dynamic maintenance of maximal points in the plane
- Space-efficient planar convex hull algorithms
- Dynamic layers of maxima with applications to dominating queries
- I/O-efficient 2-d orthogonal range skyline and attrition priority queues
- Compressing spatio-temporal trajectories
- Tangential cover for thick digital curves
- Parallel computational geometry
- Dynamic coresets
- Weighted Rectilinear Approximation of Points in the Plane
- Kinetic and dynamic data structures for convex hulls and upper envelopes
- Optimal shortest path queries in a simple polygon
- Efficient searching with linear constraints
- Off-line dynamic maintenance of the width of a planar point set
- A faster algorithm for the maximum weighted tardiness problem
- Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time
- An optimal algorithm for plane matchings in multipartite geometric graphs
- Covering moving points with anchored disks
- Fast detection of polyhedral intersection
- Dynamic half-space range reporting and its applications
- On the definition and computation of rectilinear convex hulls
- Approximating points by a piecewise linear function
- Minimizing the error of linear separators on linearly inseparable data
- Indexing moving points
- Exact algorithms for size constrained 2-clustering in the plane
- Constrained square-center problems
- The power of geometric duality
- On embedding an outer-planar graph in a point set
- In-place algorithms for computing (Layers of) maxima
- Implicitly representing arrangements of lines or segments
- Connecting colored point sets
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Tangential Cover for Thick Digital Curves
- Efficient splitting and merging algorithms for order decomposable problems.
- Ray shooting in polygons using geodesic triangulations
- A discrete geometry approach for dominant point detection
- A note on finding a maximum empty rectangle
- Parallel algorithms for some functions of two convex polygons
- Cartographic line simplication and polygon CSG formulae in \(O(n \log^* n)\) time
- An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains
- Output-sensitive results on convex hulls, extreme points, and related problems
- Finding a minimum independent dominating set in a permutation graph
- Center problems with pos/neg weights on trees
- Geometric applications of a matrix-searching algorithm
- Applications of a semi-dynamic convex hull algorithm
- On some geometric selection and optimization problems via sorted matrices
- Parallel solutions to geometric problems in the scan model of computation
- Computing shortest transversals
- Dynamic Planar Range Maxima Queries
- The two-line center problem from a polar view: a new algorithm and data structure
- Relative convex hulls in semi-dynamic arrangements
- A kinetic triangulation scheme for moving points in the plane
- Separating bichromatic point sets by L-shapes
- An efficient algorithm for maxdominance, with applications
- Convex hull properties and algorithms
- Enumerating pseudo-triangulations in the plane
- The projection median of a set of points
- On geometric optimization with few violated constraints
- Tight degree bounds for pseudo-triangulations of points
- Computing the Fréchet distance with a retractable leash
- Finding the convex hull of a sorted point set in parallel
- Compressing Spatio-temporal Trajectories
- An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem
- Covering Points with Convex Sets of Minimum Size
- Median hyperplanes in normed spaces -- a survey
- Dynamic Euclidean minimum spanning trees and extrema of binary functions
- An optimal algorithm for plane matchings in multipartite geometric graphs
- On some geometric selection and optimization problems via sorted matrices
- On the planar two-center problem and circular hulls
- Plane 3-trees: embeddability and approximation
- Output-sensitive peeling of convex and maximal layers
- Dynamic algorithms for visibility polygons in simple polygons
- A new approach to the dynamic maintenance of maximal points in a plane
- Applications of a semi-dynamic convex hull algorithm
- The density maximization problem in graphs
- A fast algorithm for the alpha-connected two-center decision problem
- Perfect binary space partitions
- Two approaches to building time-windowed geometric data structures
- Applications of mathematics to maritime search
- Title not available (Why is that?)
- On-line updating of solutions to a class of matroid intersection problems
- Dynamic convex hulls under window-sliding updates
- Maintaining AUC and \(H\)-measure over time
- On determining the on-line minimax linear fit to a discrete point set in the plane
- Dynamic connectivity in disk graphs
- Dynamic geometric data structures via shallow cuttings
- OPTIMAL LINE BIPARTITIONS OF POINT SETS
- A fast algorithm for computing sparse visibility graphs
- Determining Weak Visibility of a Polygon from an Edge in Parallel
- Computing common tangents without a separating line
- An O(log n) time parallel algorithm for triangulating a set of points in the plane
- Algorithms for problems on maximum density segment
- The maximum-level vertex in an arrangement of lines
- Parallel methods for visibility and shortest-path problems in simple polygons
- Dynamic data structures for fat objects and their applications
- Two general methods for dynamizing decomposable searching problems
- Computational geometry algorithms for the systolic screen
- k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
- MAINTAINING VISIBILITY INFORMATION OF PLANAR POINT SETS WITH A MOVING VIEWPOINT
- AN EXPERIMENTAL STUDY OF ON-LINE METHODS FOR ZONE CONSTRUCTION IN ARRANGEMENTS OF LINES IN THE PLANE
This page was built for publication: Maintenance of configurations in the plane
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1158972)
