Partitioning arrangements of lines I: An efficient deterministic algorithm
Discrete & Computational GeometryPublished 1 October 1990Open access
Pankaj K. Agarwal
Citations47
SJR quartileQ2
SJR score0.60
SNIP1.04
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A deterministic algorithm for partitioning the plane into O(r2) triangles so that no triangle meets more thanO(n/r) lines of ℒ is presented.
Abstract
In this paper we consider the following problem: Given a set ℒ ofn lines in the plane, partition the plane intoO(r 2) triangles so that no triangle meets more thanO(n/r) lines of ℒ. We present a deterministic algorithm for this problem withO(nr logn/r) running time, whereω is a constant <3.33.
Keywords
Computer ScienceEngineering
Sorting networks and their applications
2,400 Citations1968Kenneth E. Batcher
To achieve high throughput rates today's computers perform several operations simultaneously; not only are I/O operations performed concurrently with computing, but also, in multiprocessors, several computing operations are done concurrently.
American Mathematical MonthlyAlgorithms in Combinatorial Geometry.
1,801 Citations1989Jacob E. Goodman, Herbert Edelsbrunner
Algorithms in Combinatorial Geometry
1,516 Citations1987Herbert Edelsbrunner
This book offers a modern approach to computational geo- metry, an area thatstudies the computational complexity of geometric problems with an important role in this study.
Applications of random sampling in computational geometry, II
932 Citations1988Kenneth L. Clarkson
Asymptotically tight bounds for (≤k)-sets are given, which are certain halfspace partitions of point sets, and a simple proof of Lee's bounds for high-order Voronoi diagrams is given.
Discrete & Computational Geometryɛ-nets and simplex range queries
731 Citations1987David Haussler, Emo Welzl
The concept of an ɛ-net of a set of points for an abstract set of ranges is introduced and sufficient conditions that a random sample is an Â-net with any desired probability are given.
Journal of the ACMApplying Parallel Computation Algorithms in the Design of Serial Algorithms
632 Citations1983Nimrod Megiddo
It is pointed out that analyses of parallelism in computational problems have practical implications even when multi-processor machines are not available, and a unified framework for cases like this is presented.
COMBINATORICASorting inc logn parallel steps
513 Citations1983Miklós Ajtai, János Komlós +1 more
A sorting network withcn logn comparisons where in thei-th step of the algorithm the contents of registersRj, andRk, wherej, k are absolute constants then change their contents or not according to the result of the comparison.
SIAM Journal on ComputingConstructing Arrangements of Lines and Hyperplanes with Applications
444 Citations1986Herbert Edelsbrunner, Joseph O’Rourke +1 more
Discrete & Computational GeometryNew applications of random sampling in computational geometry
317 Citations1987Kenneth L. Clarkson
This paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry by creating a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from the resulting arrangement to divide and conquer.
SIAM Journal on ComputingAn Optimal-Time Algorithm for Slope Selection
138 Citations1989Richard Cole, Jeffrey S. Salowe +2 more
Given n points in the plane and an integer k, the problem of selecting that pair of points that determines the line with the kth smallest or largest slope is considered and line sweeping gives an optimal, $O(n\log n)$-time algorithm.
SIAM Journal on ComputingOn <i>k</i>-Hulls and Related Problems
137 Citations1987Richard Cole, Micha Sharir +1 more
SIAM Journal on ComputingConstructing Belts in Two-Dimensional Arrangements with Applications
118 Citations1986Herbert Edelsbrunner, Emo Welzl
The notion of a belt in A, a set of lines in the Euclidean plane, is defined, which is bounded by a subset of the edges in H, and two algorithms for constructing belts are described.
Discrete & Computational GeometryThe complexity and construction of many faces in arrangements of lines and of segments
98 Citations1990Herbert Edelsbrunner, Leonidas Guibas +1 more
The proof takes an algorithmic approach, that is, an algorithm is described for the calculation of thesem faces and the upper bound for the total number of edges is derived from the analysis of the algorithm.
Discrete & Computational GeometryPartitioning arrangements of lines II: Applications
81 Citations1990Pankaj K. Agarwal
An algorithm that preprocesses a set ofn points in the plane, into a data structure of sizeO(m) forn logn≤m≤n2, so that the number of points ofS lying inside a query triangle can be computed inO((n/√m) log3/2n) time.
Discrete & Computational GeometryConstruction of ɛ-nets
80 Citations1990Jiřı́ Matoušek
It is proved that given a setL ofn lines in the plane, the plane can be cut into O(ɛ−2) triangles in such a way that no triangle is intersected by more thanɛn lines ofL.
Discrete & Computational GeometryA fast las vegas algorithm for triangulating a simple polygon
67 Citations1989Kenneth L. Clarkson, Robert E. Tarjan +1 more
Discrete & Computational GeometryImplicitly representing arrangements of lines or segments
66 Citations1989Herbert Edelsbrunner, Leonidas Guibas +5 more
Discrete & Computational GeometryHalfspace range search: An algorithmic application ofk-sets
63 Citations1986Bernard Chazelle, F. P. Preparata
It is shown that the total number ofj-sets realized by a set ofn points inE3 isO(nk5); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.
Algorithms for diametral pairs and convex hulls that are optimal, randomized, and incremental
54 Citations1988Kenneth L. Clarkson, Peter W. Shor
An algorithm of this kind is given for computing the intersection of a set of halfspaces in three dimensions, resulting in a Las Vegas algorithm for the diameter requiring n expected time.
Discrete & Computational GeometryMore onk-sets of finite sets in the plane
54 Citations1986Emo Welzl
It is shown that there is a positive constantc such thatfK(S) is the number of subsets of S with cardinalityk εK which can be cut offS by a straight line.
Polling: a new randomized sampling technique for computational geometry
48 Citations1989John H. Reif, Subhankar Sen
A new randomized sampling technique, called Polling, is introduced which has applications to deriving efficient parallel algorithms for fundamental problems like the convex hull in three dimensions, Voronoi diagram of point sites on a plane and Euclidean minimal spanning tree.
A probabilistic algorithm for the post office problem
45 Citations1985Kenneth L. Clarkson
The algorithm employs random sampling, so the expected time holds for any set of points, and approaches the preprocessing time required for any algorithm constructing the Voronoi diagram of the input points.
SIAM Journal on ComputingRed-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
37 Citations1990Pankaj K. Agarwal, Micha Sharir
A deterministic view of random sampling and its use in geometry
31 Citations1988Bernard Chazelle, Joel Friedman
It is shown how to compute, in polynomial time, a simplicial packing of sizeO(rd) which coversd-space, each of whose simplices intersectsO(n/r) hyperplanes, and improves on various probabilistic bounds in geometric complexity.