NDLI: Lines in space-combinators, algorithms and applications

Please wait, while we are loading the content...

Multiparty protocols and logspace-hard pseudorandom sequences

Pseudo-random generation from one-way functions

A hard-core predicate for all one-way functions

Universal one-way hash functions and their cryptographic applications

Limits on the provable consequences of one-way permutations

A zero-one law for Boolean privacy

Verifiable secret sharing and multiparty protocols with honest majority

Designing programs that check their work

Provably fast integer factoring with quasi-uniform small quadratic residues

Functional interpretations of feasibly constructive arithmetic

Expressiveness of restricted recursive queries

On Ω-automata and temporal logic

Quantifier elimination in the theory of an algebraically-closed field

Probabilistic computation and linear time

The ismorphism conjecture fails relative to a random oracle

On the method of approximations

On the extended direct sum conjecture

Circuits and local computation

A general sequential time-space tradeoff for finding unique elements

On the theory of average case complexity

Tradeoffs between communication and space

Work-preserving emulations of fixed-connection networks

An O(logN) deterministic packet routing scheme

Fast computation using faulty hypercubes

Optimal size integer division circuits

On the complexity of radio communication

Local reorientation, global order, and planar topology

Parallel depth-first search in general directed graphs

Highly parallelizable problems

Optimal separations between concurrent-write parallel machines

CREW PRAMS and decision trees

Implicit O(1) probe search

The cell probe complexity of dynamic data structures

On aspects of university and performance for closed hashing

Verifying partial orders

A random polynomial time algorithm for approximating the volume of convex bodies

Lines in space-combinators, algorithms and applications

Polling: a new randomized sampling technique for computational geometry

Coordinate representation of order types requires exponential storage

Inference of finite automata using homing sequences

The minimum consistent DFA problem cannot be approximated within and polynomial

Crytographic limitations on learning Boolean formulae and finite automata

Proof of a conjecture of R. Kannan

Bounded concurrrent time-stamp systems are constructible

On the improbability of reaching Byzantine agreements

Compact distributed data structures for adaptive routing

Randomized distributed shortest paths algorithms

On search decision and the efficiency of polynomial-time algorithms

A new fixed point approach for stable networks stable marriages

Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs

An $O(n^{0.4})-approximation$ algorithm for 3-coloring

Trading space for time in undirected s-t connectivity

Expanding graphs and the average-case analysis of algorithms for matchings and related problems

Lower bounds on the length of universal traversal sequences

The electrical resistance of a graph captures its commute and cover times

On the second eigenvalue of random regular graphs

Lines in space-combinators, algorithms and applications

Content Provider	ACM Digital Library
Author	Chazelle, B. Guibas, L. Sharir, M. Edelsbrunner, H.
Abstract	We study combinatorial and algorithmic problems involving arrangements of n lines in 3-dimensional space, and then present applications of our results to a variety of problems on polyhedral terrains. Our main results include:A tight &THgr;(n2) bound on the complexity of the space of all lines passing above all the n given lines (their “upper envelope”) and satisfying a certain orientation consistency constraint.A preprocessing procedure using near-quadratic time and storage that builds a structure supporting &Ogr;(log n) time queries for testing if a line lies above all the given lines.An &Ogr;(n4/3+ε) randomized expected time algorithm, for any fixed ε > 0, that tests the “towering property”: do n given red lines lie all above n given blue lines?A preprocessing procedure for a polyhedral terrain &Sgr; with n edges, that uses near-quadratic time and storage and builds a structure supporting &Ogr;(log2 n) time rayshooting queries for computing the first intersection of an arbitrary query ray with &Sgr;.Finding the smallest vertical distance between two disjoint polyhedral terrains with a total of n edges, in time &Ogr;(n4/3+ε), for any ε > 0.Computing the upper envelope (pointwise maximum) of two polyhedral terrains with a total of n edges, in time &Ogr;(n1.5+ε + klog2 n), for any ε > 0, where &kgr; is the size of the output envelope.The tools used to obtain these results include Plücker coordinates for lines in space, random sampling in geometric problems, and a new variant of segment trees.
Starting Page	382
Ending Page	393
Page Count	12
File Format	PDF
ISBN	0897913078
DOI	10.1145/73007.73044
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1989-02-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Categorical Combinators, Sequential Algorithms, and Functional Programming, Second Edition

Arrangements of lines in 3-space: a data structure with applications

Generalized combinators in functional languages and their applications

VDM semantics of programming languages: combinators and monads

Accelerating parser combinators with macros

Total parser combinators

Algebraic Combinators for Data Dependencies and Their Applications

Programming Deep Concurrent Constraint Combinators (2000)

Programming deep concurrent constraint combinators (2000)

Lines in space-combinators, algorithms and applications

Similar Documents

Categorical Combinators, Sequential Algorithms, and Functional Programming, Second Edition

Arrangements of lines in 3-space: a data structure with applications

Generalized combinators in functional languages and their applications

VDM semantics of programming languages: combinators and monads

Accelerating parser combinators with macros

Total parser combinators

Algebraic Combinators for Data Dependencies and Their Applications

Programming Deep Concurrent Constraint Combinators (2000)

Programming deep concurrent constraint combinators (2000)

Lines in space-combinators, algorithms and applications