NDLI: Kinetic sorting and kinetic convex hulls

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

Forbidden patterns and unit distances

Mountain reduction, block matching, and applications in intensity-modulated radiation therapy

Certifying and constructing minimally rigid graphs in the plane

An exact, complete and efficient implementation for computing planar maps of quadric intersection curves

Smaller coresets for k-median and k-means clustering

Cache-oblivious planar orthogonal range searching and counting

Learning smooth objects by probing

A time-optimal delaunay refinement algorithm in two dimensions

Inclusion-exclusion formulas from independent complexes

Vertical ray shooting for fat objects

Minimum dilation stars

Learning smooth objects by probing

Clustered planarity

Hadwiger and Helly-type theorems for disjoint unit spheres in $R^{3}$

Dynamic maintenance of molecular surfaces under conformational changes

Pointed and colored binary encompassing trees

On the exact computation of the topology of real algebraic curves

Improved approximation algorithms for geometric set cover

Cache-oblivious R-trees

Provable dimension detection using principal component analysis

Star splaying: an algorithm for repairing delaunay triangulations and convex hulls

Weak feature size and persistent homology: computing homology of solids in $R^{n}$ from noisy data samples

The skip quadtree: a simple dynamic data structure for multidimensional data

Finding the best shortcut in a geometric network

Reconstructing collections of arbitrary curves

Double-permutation sequences and pseudoline transversals

Incidences of not-too-degenerate hyperplanes

The lifting model for reconfiguration

Abstract order type extension and new results on the rectilinear crossing number

Shortest path amidst disc obstacles is computable

Sampling in dynamic data streams and applications

Multi-pass geometric algorithms

Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based surface reconstruction

Stability of persistence diagrams

Space efficient dynamic orthogonal range reporting

Energy-aware stage illumination

Efficient geometric techniques for reconstructing 3D vessel trees from biplane image

Almost tight bound for a single cell in an arrangement of convex polyhedra in $R^{3}$

The visibility--voronoi complex and its applications

Fast construction of nets in low dimensional metrics, and their applications

Kinetic sorting and kinetic convex hulls

Inequalities for the curvature of curves and surfaces

Efficient computation of query point visibility in polygons with holes

Guarding a terrain by two watchtowers

Implementing time-varying contour trees

Curvature-bounded traversals of narrow corridors

Maximizing the overlap of two planar convex sets under rigid motions

Rectangular cartograms: construction & animation

Animation of curve constrained drawings of planar graphs

Covering points with a polygon

1-link shortest paths in weighted regions

An extension of CGAL to the oriented projective plane $T^{2}$ and its dynamic visualization system

Exact minkowski sums of convex polyhedra

Fast and reliable collision detection using graphics processors

Kinetic sorting and kinetic convex hulls

Content Provider	ACM Digital Library
Author	de Berg, Mark Abam, Mohammad Ali
Abstract	Let S be a set of n points moving on the real line. The kinetic sorting problem is to maintain a data structure on the set S that makes it possible to quickly generate a sorted list of the points in S, at any given time. We prove tight lower bounds for this problem, which show the following: with a subquadratic maintenance cost one cannot obtain any significant speed-up on the time needed to generate the sorted list (compared to the trivial O(n log n) time), even for linear motions.We also describe a kinetic data structure for so-called gift-wrapping queries on a set S of n moving points in the plane: given a point q and a line l through q such that all points from S lie on the same side of l, report which point pi ∈ S is hit first when l is rotated around q. Our KDS allows a trade-off between the query time and the maintenance cost: for any Q with 1 ≤ Q ≤ n, we can achieve O(Q log n) query time with a KDS that processes $O(n^{2+ε/Q^{1+1/δ}})$ events, where δ is the maximum degree of the polynomials describing the motions of the points. This allows us to reconstruct the convex hull quickly when the number of points on the convex hull is small. The structure also allows us to answer extreme-point queries (given a query direction ⃗d, what is the point from S that is extreme in direction ⃗d?) and convex-hull containment queries (given a query point q, is q inside the current convex hull?).
Starting Page	190
Ending Page	197
Page Count	8
File Format	PDF
ISBN	1581139918
DOI	10.1145/1064092.1064122
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Lower bounds Kinetic convex hulls Kinetic data structures Kinetic sorting
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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